Longest Increasing Sequence using Divide and Conquer

Revision en2, by rahul_1234, 2016-01-10 21:04:42

Given an array A of n numbers, we want to select a sub-sequence of A such that each number in the sub-sequence is at least as large as the previous one, and such that the length of this sub-sequence is as large as possible. Give a divide-and-conquer algorithm for this problem. What is the running time of your algorithm?

I got this explanation but could not understand:

A natural algorithm is to divide the problem into n problems of size n/2, where for problems on the left, we compute the longest increasing subsequence ending at a given position, for the ones on the right we want to compute the longest increasing subsequence with a given element as the smallest. The recursion is therefore T(n) = nT(n/2) + O(1).

So please explain this to me. I'll be thankful to you.

Tags divide and conquer

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English rahul_1234 2016-01-10 21:06:08 4 Tiny change: 's of size n/2, where fo' -> 's of size **n/2**, where fo'
en2 English rahul_1234 2016-01-10 21:04:42 2 Tiny change: ' of size n=2, where f' -> ' of size n/2, where f'
en1 English rahul_1234 2016-01-10 18:05:49 842 Initial revision (published)