300. 最长上升子序列（坐标dp）

链接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(vectorint nums) { if (nums.size() 0) return 0; // dp[i] 表示到下表为i,nums[i]最长上升子序列长度 vectorint 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(vectorint nums) { int len nums.size(); vectorint dp(len, 1); vectorint 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; } };