Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such that
A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible.
The sequence S1, S2, …, Sk is called an arithmetic progression if
Sj+1 – Sj is a constant
{2,3,5,7,8,11}
DP solution with O(n^3).
Assume, we've optimum solution for array a[0,1,2,....,k]. To get solution for index = k+1, we can put a[k+1] next in a sequence ending with a[j] for 0 <= j <= k.
So, if diff = a[k+1] - a[j], we need to look up sub-problem solution for index = j to search for diff, and taking the max value to get a maximum sequence.
code input/output:
{2,3,5,7,8,11};
max seq: 2, 5, 8, 11
DP array values:
0 0 0 0 0 0
1 0 0 0 0 0
1 1 0 0 0 0
1 1 2 0 0 0
1 1 2 1 0 0
1 1 1 2 3 0
