Btw...this is O(n*log n) (query and update in the segment tree each
take O(log n))
On Dec 31, 11:26 am, suhash <suhash.venkat...@gmail.com> wrote:
> 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 <bhupendra....@gmail.com> 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 <prabaf...@gmail.com> wrote:
> > > You can use binary search
>
> > > On 12/31/10, Anand <anandut2...@gmail.com> 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 algoge...@googlegroups.com.
> > > > To unsubscribe from this group, send email to
> > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> > > .
> > > > 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 algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> > > .
> > > 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 algoge...@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.
