For longest increasing subword, this O(n) solution is correct.
For longest increasing subsequence, it can be found in O(n*log n)
using binary search or segment tree.
Here is the segment tree approach.
Assume input is a[1....n]
Let the property of the segment tree be: stores maximum value in a
range.
Now, we need a segment tree with max(a[1],a[2],...a[n]) nodes (It can
be reduced to 'n' nodes by mapping values)
eg:- if a[]={1,2,99,3,7}, we need a segment tree with '99' nodes
(numbered 1 to 99).
Initially, all leaf nodes of the segment tree have a value 0.
Now, process the elements of 'a' in order.
ans=0
For each position 'i', do the following:
query the segment tree for maximum in the range [1,a[i]-1]. Let this
value be 'v'.
update the value of the leaf node at position a[i] (not position 'i')
to v+1.
ans=max(ans,v+1)
'ans' stores the final answer for length of longest ascending
subsequence.
eg:- Let a[]={1,3,2,5}
ans=0
Initial tree(leaf nodes): 0 0 0 0 0
At i=0: v=0, ans=1
new tree: 1 0 0 0 0
At i=1: v=1, ans=2
new tree: 1 0 2 0 0
At i=2: v=1, ans=2
new tree: 1 1 2 0 0
At i=3: v=2, ans=3
new tree: 1 1 2 0 3
Therefore, ans=3.
Now, the last part: reducing the size of segment tree to 'n' nodes
Let a[]={1,2,99,5,8}
Map the values in ascending order: 1=>1, 2=>2, 5=>3, 8=>4, 99=>5
Hence, the new array a' becomes {1,2,5,3,4}
Now, segment tree for this has only 'n' (5) nodes, compared to 99
earlier.
It is easy to note that solutions for arrays a and a' are same.
On Dec 31, 9:07 am, bhupendra dubey <[email protected]> wrote:
> It can be done in O(n) time.
>
> int start_index=0, longest_sequence=0
>
> traverse the sequence and increment 't' for every a[i+1]>a[i]
> starting with zero till this holds true.
>
> assign 't' to longest_sequence
>
> assuming condition evaluates to false for a[k];
> repeat the above step but assign 't' to longest_sequence only when
> t>longest_sequence
> also change start_index to 'k'
>
> do this for the whole array.
>
>
>
> On Fri, Dec 31, 2010 at 8:20 AM, Prabakaran N <[email protected]> wrote:
> > You can use binary search
>
> > On 12/31/10, Anand <[email protected]> wrote:
> > > Anyone know how to find longest increasing subsequence in O(nlogn)
> > > complexity?
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected]<algogeeks%[email protected]>
> > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected]<algogeeks%[email protected]>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> bhupendra dubey
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
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.
