Longest Increasing Subsequence
給定一個數(shù)組篮条，找出longest increasing subsequence的長度
這個solution用dynamic programming(DP)方法。
首先，使用vector<int> res來記錄當前l(fā)ongest increasing subsequence.
然后遍歷nums, 如果res中沒有比當前元素n大的元素指蚜，就說明n可以作為subsequence新的最后一個元素啦撮，以此來增加subsequence的長度卸勺。如果res中有比n大的元素奸焙，說明n并不能用來增加subsequence的長度，但是不能就這樣丟棄n献烦，因為n及n后面的一些元素很有可能替代現(xiàn)在res中的一些元素構(gòu)成更長的subsequence滓窍，所以我們做一個不影響最后長度且能更新元素的方法：用n來替換res中第一個比n大的元素。
最后返回res.size()
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> res;
for (auto n: nums) {
auto it = lower_bound(res.begin(), res.end(), n);
if (it == res.end()) res.push_back(n);
else *it = n;
}
return res.size();
}
};
