### rahul_1234's blog

By rahul_1234, history, 4 years ago, ,

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.

• -12

 » 4 years ago, # | ← Rev. 2 →   +1 I don't understand this explanation as well. Moreover, it seems incorrect, as longest subsequence in the left is not neccessary to be the part of the longest subsequence of all sequence.2 1 7 8 | 3 4 5 6As you find 2 7, 2 8, 1 7 or 1 8 as a LIS for left part, you'll probably get WA since correct length is 5.You can easily compute longest increasing subsequence with Fenwick or Segtree, but I doubt it's the case in your task.
•  » » 4 years ago, # ^ |   0 I have made a little edit in explanation, it would be n/2 and not n=2. Now can u plz see it again?
 » 4 years ago, # |   0 Auto comment: topic has been updated by rahul_1234 (previous revision, new revision, compare).
 » 4 years ago, # |   0 I will use Miyukine's test to explain what I understood from the explanation: 2 1 7 8 | 3 4 5 6Let's consider the first half — (2,1,7,8). We will find the longest increasing subsequence ending in each number (let's say L[i]). So L[2] is 1, L[1] is 1, L[7] is 2 and L[8] is 3.Now similarly for the second half — (3,4,5,6), we will find the longest increasing subsequence starting in each number (let's say R[i]). So R[6] is 1, R[5] is 2, R[4] is 3 and R[3] is 4. How to compute L, R? Well, L[X]=1+max(L[1],L[2],...L[X-1]) and R[X]=1+max(R[X+1],R[X+2],...,R[MAXVAL]). It can be done with a binary indexed tree in O(NlogN) or in O(N^2) using a naive algorithm.What remains is to see how to get the answer for the sequence. It's quite easy, let's fix some index i on the left side. The answer for this index will be L[i]+max(R[A[i]+1],R[A[i]+2],...R[MAXVALUE]) and the whole answer will be the maximum among the answers for all indices. For example ANS[1] (index 1, not value) will be L[2]+R[3]=5, ANS[2] will be L[1]+R[3]=5, ANS[3] will be L[7]+0=1 and ANS[4] will be L[8]+0=1, so the final answer is 5 :)
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Okay thanks a lot for nice explanation. Can u plz tell how one can get recursion T(n) = nT(n/2) + O(1) from the above explanation?
•  » » 4 years ago, # ^ |   0 Minor Correction: In the last paragraph, you meant L[A[i]] instead of L[i] probably
 » 4 years ago, # | ← Rev. 2 →   0 Please somebody guide me how one will get the following recurrence relation T(n) = nT(n/2) + O(1) ?
 » 13 months ago, # |   -18 I think its O(n^log(n)) which is really more than O(n^2)