Last week in an interview I was asked the above question and as expected I wasn't able to answer it correctly, later on when I checked I saw that its a dynamic programming based algorithm. I am not proficient in dynamic programming but suppose I was to design this algorithm then how should I approach it?
Suppose, I take idea from other divide and conquer algorithms like MergeSort and design the solution something like:
Obviously there are missing pieces, but how get forward from here?
Your proposal won't work, because the longest sequences in both halves usually won't be contiguous, and there could exist a longer sequence when you join the halves.
You can fix this as follows:
in both halves, find the longest increasing sub-sequence, let L and R;
in both halves, find the longest increasing sub-sequence which is left-aligned, let LL and RL;
in both halves, find the longest increasing sub-sequence which is right-aligned, let LR and RR;
for the longest, keep the longest of L, R, LR+RL if the latter forms an increasing sequence;
for the left-aligned, keep LL or the whole left sub-sequence + RL if this forms an increasing sub-sequence;
for the right-aligned, keep RR or LR + the whole right sub-sequence if this forms an increasing sub-sequence.
All these operations are done in a single recursive process. When you concatenete two sub-sequences, checking if they form an increasing sub-sequence just takes the comparison of the facing elements.
Update:
This "fix" was not thoroughly checked.