Ideas for Bamboo Art
Sort the input array A
DP[i][j] = Max Length Arithmetic Progression ending at index i with second last element as index j
Observe that fixing the last element and second last element gives us the common difference D = A[i] - A[j] of the AP.
Also, observe that all elements in A are distinct! We can use this to our advantage to speed up the DP.
Let L[i] = Index of occurrence of the number i in the sorted array A
Now, the recurrence is as follows:
DP[i][j] = DP[j][L[A[j]-D]] + 1 , where D = A[i] - A[j]
Ans = max( DP[i][j] ) for all i,j where i > j
The complexity of this solution would be O(n^2)