Finding longest arithmetic progressions

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(n2) time, which is optimal in the worst case in the 3-linear decision tree model. A second divide-and-conquer algorithm runs in O((n2/k) log (n/k) log k) time, where k is the output size.

Publications - Jeff Erickson ( 15 Nov 1999