use divide and conquer to solve Longest Increasing Subsequence problem

Longest Increasing Subsequence 最常见的就是用Dynamic Programming，通常用这个recurrence relation:A(i) = 1 + max{A(j)| 1 ≤ j < i and a_j < a_i}. 用divide and conquer方法在写recurrence relation的时候不同，要首先假设a是LIS中的一员，for all the i, recursively solve the right and left side of a[i], find the longest one. 第一眼貌似挺好写的，可是问题是怎么track the largest element in the left part LIS and the smallest element in the right part LIS.[/i]