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.
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 6
As 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 will use kpw29's test to explain what I understood from the explanation: 2 1 7 8 | 3 4 5 6
Let'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 :)
Minor Correction: In the last paragraph, you meant L[A[i]] instead of L[i] probably
I think its O(n^log(n)) which is really more than O(n^2)