@Divye Sir
I just came to know this is not a general Algorithm
This works only for sorted Array
this is Some description about the algo in paper
this algo uses the property of a AP that for every 3 consecutive elements of
an AP(a1,a2,a3)
a1+a3 = 2*a2
*L[i j] stores the maximum length of an arithmetic progression* *whose
first two terms are respectively A[i] and A[j].* (so we know about diff of
the AP that this sequence will form for each i,j)
this Algo starts with considering all possible a2's and tries to extend the
current AP formed by A[j] and A[k].
if(a[i] + a[k] == 2*a[j]) that means a[i] forms an AP with A[j] and A[k]
if(a[i] + a[k] < 2*a[j]) a[i] can not form AP with A[i] and A[j] look for
greater k
if(a[i] + a[k] > 2*a[j]) then a[i] does not form AP but we need a smaller
A[i] so value of L[i,j] = 2
And about Your Algorithm
L[0,j] part seems to be right
but for L[i,j] part i think it will go O(n^3)...........i am not getting it
:(
On Sun, Jul 10, 2011 at 11:39 PM, DK <divyekap...@gmail.com> wrote:
> 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.
>
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
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.
