Abstract:

We describe efficient algorithms to find the longest arithmetic progression in a given set of numbers. We first present a dynamic programming algorithm that runs in O(n^{2}) time, which is optimal in the worst case in the 3-linear decision tree model. A second divide-and-conquer algorithm runs in O((n^{2}/k) log (n/k) logk) time, wherekis the output size.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 15 Nov 1999