Never mind. Figured it out, though in possibly different from the paper. Principle of optimality to the rescue! :) O(n^2)
DP equations: LAP[i, j] = Longest AP in range [i,j] of the sequence LAP[0, j] = max{LAP[0, k] (for all k in range [0, j-1]) extended with a[j],1 (the element a[j] itself)} Result in LAP[0,n-1] Make sure LAP maintains information about last element and common difference. (The simple cubic DP can be reduced to N^2 by observing that LAP[i,j] is essentially the same as LAP[0, j] by principle of optimality as the result needs to be calculated with start index 0). @Sunny: Any bugs in the analysis? -- 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/-/lX0_4pjCKJgJ. 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.