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.