Longest Arithmetic Progression

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