題目：
Given an unsorted array of integers, find the length of longest increasing subsequence.
For example, Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. 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?
解答：
尋找最長上升子序列（LIS），最基本的方法是動態規劃。轉移方程為 dp[i] = max{dp[j]} + 1 ( -1< j < i && nums[j] < nums[i])。
解釋也非常直觀：dp[i] 表示如果取得當前 i 元素，所能達到的最長 LIS。如果需要打印出此序列，僅需要保存上一個元素。
class Solution {
public:
int lengthOfLIS(vector& nums) {
int size = nums.size();
if (size <= 1) return size;
vector dp(size, 1);
int maxlen;
for (int i = 1; i < size; i++) {
maxlen = 0;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i] && maxlen < dp[j]) maxlen = dp[j];
}
dp[i] = maxlen + 1;
}
maxlen = 0;
for (int i = 0; i < size; i++) {
if (dp[i] > maxlen) maxlen = dp[i];
}
return maxlen;
}
};
如果要修改到 O(n log n) time complexity？貪心法 + 二分搜索。
增加一條輔助的順序（ordered）棧（隊列……完成任務就好），保存盡可能長的LIS。入棧的要求為：
將a[0]入棧每次取棧頂元素top（最大元素）和讀到的元素a[i](0
直觀理解：對於 x 和 y，如果 x < y 且 stack[y] < stack[x]，用 stack[x] 替換 stack[y]，此時的最長序列長度沒有改變，但序列繼續變長的''潛力''增大，這就是貪心的目標。
舉例：原序列為1，5，8，3，6，7
開始1，5，8相繼入棧，此時讀到3，用3替換5，得到1，3，8；再讀6，用6替換8，得到1，3，6；再讀7，得到最終棧為1，3，6，7。最長遞增子序列為長度4
但是這個方法，有一個很大的缺陷：只能保證序列長度的正確性，不能保證棧中就是正確的序列。
舉例：原序列為1，5，8，2，棧內最後是 1，2，8 不是正確的序列。
分析一下，我們可以看出，雖然有些時候這樣得不到正確的序列，但最後算出來的個數是沒錯的，為什麼呢？
當a[i]>top時，總個數直接加1，這肯定沒錯；但當a[i]
class Solution {
public:
int lengthOfLIS(vector& nums) {
vector LIS;
for (int i = 0; i < nums.size(); i++) {
if (LIS.size() == 0 || LIS[LIS.size() - 1] < nums[i]) {
LIS.push_back(nums[i]);
}
else {
int l = 0, r = LIS.size() - 1;
while (l < r) {
int m = (l + r) / 2;
if (LIS[m] >= nums[i]) {
r = m;
}
else {
l = m + 1;
}
}
LIS[l] = nums[i];
}
}
return LIS.size();
}
};
