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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
