以LeetCode-300为例：
O(n^2)解法：
dp数组表示以i结尾的最长递增子序列的长度
class Solution {
public:int lengthOfLIS(vector<int>& nums) {const int size = nums.size();if (size == 0) { return 0; } vector<int> dp(size, 1);int res = 1;for (int i = 1; i < size; ++i) {for (int j = 0; j < i; ++j) {if (nums[j] < nums[i]) {dp[i] = max(dp[i], dp[j]+1);}}res = max (res, dp[i]);}return res;}
};
O(nlogn)解法：
tails[i]数组定义：长度为i+1最长递增子序列的最小值末尾值
以nums[4,5,6,3]为例
len = 1 : [4], [5], [6], [3] => tails[0] = 3
len = 2 : [4, 5], [5, 6] => tails[1] = 5
len = 3 : [4, 5, 6] => tails[2] = 6很容易判断tails数组递增，可以应用二分法(1) if x is larger than all tails, append it, increase the size by 1
(2) if tails[i-1] < x <= tails[i], update tails[i]class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> tails(nums.size(),0);int size=0;for(int t=0;t<nums.size();t++){int i=0,j=size;while(i!=j){int mid=(i+j)/2;if(tails[mid]<nums[t])i=mid+1;else j=mid; // 注意这里为了取到右端的值}tails[i]=nums[t];if(i==size)size++;}return size;}
};
