@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 [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.
