@Sunny: We don't need ever to calculate generic L[i,j] as we can do this problem by simply calculating L[0,j] which reduces the dimensionality of the problem. Here's a modified solution on the same lines as the one originally proposed. Version 2 uses hash table. Complexity is O(N^2) (if hash table management are O(1))
1. Create a (hash) table LAP[0, j, d] (the zero index being a constant, d being a common difference of the AP, all elements initially zero). The range of d is D = dmax - dmin (both parameters can be found in O(N^2) if required) 2. For every a[j] { For every a[i] before a[j] in the array { // O(N) loop LAP[0, j, a[j] - a[i]] = max{LAP[0, i, a[j] - a[i]] + 1, LAP[0,j,a[j]-a[i]]} // O(1) step } } The above step in English: For the current element a[j], consider all prior elements a[i]. Find the common difference with the element a[i]. Check a[i]'s hash table and see what was the LAP with that common difference. Extend that LAP by 1 element. 3. The maximum value present among all the hash tables is the answer. O(N D) search. If you want the sequence, it is straightforward to maintain a parent pointer array along with the LAP array in the inner loop. Time Complexity: O(N^2 + N D) where D = dmax - dmin (where dmax and dmin are the max and min common differences in the array respectively). Space Complexity: O(N D). This seems to look much better. If we use a map instead of a hash table, complexity will be O(N^2 log N) guaranteed. Also, this solution doesn't require sorted sequences as the paper. @Sunny: Looks okay? -- DK http://twitter.com/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/jRWYKk5G55sJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.