[LeetCode] Longest Increasing Subsequence解題思路實作代碼

given an unsorted array of integers, find the length of longest increasing subsequence.

for example,

given <code>[10, 9, 2, 5, 3, 7, 101, 18]</code>,

the longest increasing subsequence is <code>[2, 3, 7, 101]</code>, therefore the length is <code>4</code>. note that there may be more than one lis combination, it is only necessary for you to return the length.

your algorithm should run in o(n2) complexity.

follow up: could you improve it to o(n log n) time complexity?

思路1：動态規劃o(n2)。i為遞增子序列的末尾元素的位置，依次周遊i之前的位置，更新其值。

思路2：動态規劃+二分搜尋o(nlgn)。用一個附加數組儲存遞增序列的尾元素，依次周遊原數組中的元素，将其插入到附加數組中的正确位置，若插入最後一個元素之後，則更新最長遞增子序列的長度。

c++動态規劃法實作代碼如下:

c++動态規劃+二分法實作代碼：

java實作代碼：