Hmm... got your point.
I know how to that with O(N^2) algorithm - it generates array, let it be seq, and seq(i) means: 'what is the maximum length of LDS finishing on element i'
This can be done in O( N * log(L) ) as well.
Lets see how it works:
We need 3 arrays:
1. A[] = {4 3 2 1 1002 1000} (this is the input array after reversing)
2. seq[] = ( seq[
i] means - 'what is the maximum length of LDS finishing on element
i)
3. abc[] = ( this is a helper array and it guides us to create the seq[] ) Excuse my nomenclature, it is usually very crappy.
Initially both
seq and
abc arrays are empty. For each element that we iterate in A[], we have to fill the corresponding index in the seq[] and update abc[] accordingly. After everything is complete, seq[] will have the same number of elements as that of array[], but abc[] will have a cardinality equaling the value of LDS.
For the sake of convenience, we are using 1 base index.
#1 - 4
For the first number just set seq[1] with 1 and abc[1] with 4.
seq[] = {1}
abc[] = {4}
#2 - 3
Look for the smallest number in abc[] whose value is > 3 and place it right after that.
We have 4 and so place 3 on the right side of 4. seq[] will be appended with the index of the value in abc[] were just placed 3. It is the 2nd index and thus seq[] will be appended with 2.
seq[] = {1, 2}
abc[] = {4, 3)
#3 - 2
Look for the smallest number in abc[] whose value is >2 and place it right after that.
seq[] gets updated with the index in abc[] where we place 2.
seq[] = {1, 2, 3}
abc[] = {4, 3, 2}
#4 - 1
Look for the smallest number in abc[] whose value is >1 and place it right after that.
seq[] = {1, 2, 3, 4}
abc[] = {4, 3, 2, 1}
#5 - 1002
Now then. Look for the smallest number in abc[] > is 1002. There is no such number and so place it at index 1.
seq[] gets updated with the index of 1002 in abc[].
seq[] = {1, 2, 3, 4, 1}
abc[] = {1002, 3, 2, 1} (note that we are replacing 1002 and not inserting)
#6 - 1000
The smallest value larger than 1000 in abc[] is 1002 and it as at index #1. So we place 1000 at #2 in abc[]
seq[] = {1, 2, 3, 4, 1, 2}
abc[] = {1002, 1000, 2, 1}
Here you go.
abc[] is always sorted. So when we are searching for smallest value in abc[] larger than 'X', we can use binary search and thus that results in an overall complexity of O( N * log(L) ) .
With the resultant seq[], you can find the required result in O(N).
The explanation could be a little disarrayed, but hope it helps nonetheless.