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(n²) 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²/k) log (n/k) log k) time, where k is the output size.