链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/submissions/

解题思路：
状态定义：

dp[i] 的值代表 nums 前 i 个数字的最长子序列长度。
转移方程： 设 j∈[0,i)，考虑每轮计算新 dp[i] 时，遍历 [0,i) 列表区间，做以下判断：

当 nums[i]>nums[j] 时： nums[i] 可以接在 nums[j] 之后（此题要求严格递增），此情况下最长上升子序列长度为 dp[j]+1 ；
当 nums[i]<=nums[j] 时： nums[i] 无法接在 nums[j]nums[j] 之后，此情况上升子序列不成立，跳过。
上述所有 1. 情况 下计算出的 dp[j]+1 的最大值，为直到 i 的最长上升子序列长度（即 dp[i] ）。实现方式为遍历 j 时，每轮执行 dp[i] = max(dp[i], dp[j] + 1)。
转移方程： dp[i] = max(dp[i], dp[j] + 1) for j in [0, i) 。

初始状态：

dp[i]所有元素置 1，含义是每个元素都至少可以单独成为子序列，此时长度都为 1 。

返回值：

返回 dp列表最大值，即可得到全局最长上升子序列长度。

复杂度分析：

时间复杂度 O(N^2) ： 遍历计算 dpdp 列表需 O(N) ，计算每个 dp[i]dp[i] 需 O(N) 。
空间复杂度 O(N) ： dp列表占用线性大小额外空间。

class Solution { public: int lengthOfLIS(vector<int>& nums) { if (nums.size() == 0) return 0; // dp[i] 表示到下表为i,nums[i]最长上升子序列长度 vector<int> dp(nums.size()); int lis = 1; dp[0] = 1; for (int i = 1; i < nums.size(); ++i) { int max_dp = 0; //0 <=j < i,遍历左右dp[j],找到在nums[i]时候,的最长上升子序列长度 for (int j = 0; j < i; ++j) { if (nums[i] > nums[j]) { max_dp = max(max_dp, dp[j]); } } // 更新dp[i]最长上升子序列 dp[i] = max_dp + 1; // 更新最长上升子序列 lis = max(lis, dp[i]); } return lis; } };

class Solution { public: int lengthOfLIS(vector<int>& nums) { int len = nums.size(); vector<int> dp(len, 1); vector<int> prev(len, -1); int max_result = 1; int end = 0; for (int i = 0; i < len; ++i) { prev[i] = i; for (int j = 0; j < i; ++j) { if (nums[i] > nums[j]) { if (dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; prev[i] = j; } } } if (dp[i] > max_result) { max_result = dp[i]; end = i; } } int k = end; cout << nums[end] << " "; while (prev[k] != k) { cout << nums[prev[k]] << " "; k = prev[k]; } // cout << nums[dp[k]] ; return max_result; } };