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.  Comments (8)
 » 4 years ago, # | ← Rev. 2 →   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.
•  » » I have made a little edit in explanation, it would be n/2 and not n=2. Now can u plz see it again?
 » Auto comment: topic has been updated by rahul_1234 (previous revision, new revision, compare).
 » 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 is 1, L is 1, L is 2 and L 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 is 1, R is 2, R is 3 and R is 4. How to compute L, R? Well, L[X]=1+max(L,L,...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 (index 1, not value) will be L+R=5, ANS will be L+R=5, ANS will be L+0=1 and ANS will be L+0=1, so the final answer is 5 :)
•  » » 4 years ago, # ^ | ← Rev. 2 →   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?
•  » » Minor Correction: In the last paragraph, you meant L[A[i]] instead of L[i] probably
 » 4 years ago, # | ← Rev. 2 →   Please somebody guide me how one will get the following recurrence relation T(n) = nT(n/2) + O(1) ?
 » I think its O(n^log(n)) which is really more than O(n^2)