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.**