题目描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。
eg:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。思路描述：定义 dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度，注意 nums[i]必须被选取。
$$ 我们从小到大计算 dp[] 数组的值，在计算 dp[i]之前，我们已经计算出 dp[0 \ldots i-1]dp[0…i−1] 的值，\则状态转移方程为：
dp[i] = \text{max}(dp[j]) + 1,\ \text{其中} , 0 \leq j < i , \text{且} , \textit{num}[j]<\textit{num}[i], dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i],\
即考虑往 dp[0 \ldots i-1]中最长的上升子序列后面再加一个 \textit{nums}[i]。由于 dp[j] 代表 \textit{nums}[0 \ldots j] \中以 \textit{nums}[j]结尾的最长上升子序列，所以如果能从 dp[j] 这个状态转移过来，\那么 \textit{nums}[i]必然要大于 \textit{nums}[j]，才能将 \textit{nums}[i] 放在 \textit{nums}[j]后面以形成更长的上升子序列。 \ 最后，整个数组的最长上升子序列即所有 dp[i] 中的最大值。\
\text{LIS}_{\textit{length}}= \text{max}(dp[i]), \text{其中} , 0\leq i < n, LIS length =max(dp[i]),其中0≤i<n $$
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n=(int)nums.size();
if (n == 0) return 0;
vector<int> dp(n, 0);
for (int i = 0; i < n; ++i) {
dp[i] = 1;
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
};考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int len = 1, n = (int)nums.size();
if (n == 0) return 0;
vector<int> d(n + 1, 0);
d[len] = nums[0];
for (int i = 1; i < n; ++i) {
if (nums[i] > d[len]) d[++len] = nums[i];
else{
int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
while (l <= r) {
int mid = (l + r) >> 1;
if (d[mid] < nums[i]) {
pos = mid;
l = mid + 1;
}
else r = mid - 1;
}
d[pos + 1] = nums[i];
}
}
return len;
}
};