最长递增子序列典型应用题目详解

如你所知最长递增子序列问题要求在数组中找到一个递增的子序列使其长度最大。典型题目最长递增子序列题目描述给定一个整数数组找到其中最长严格递增子序列的长度。思路定义 dp[i] 为考虑前 i 个元素以第 i 个数字结尾的最长上升子序列的长度注意 nums[i] 必须被选取。那么从小到大计算 dp 数组的值在计算 dp[i] 之前已经计算出 dp[0…i−1] 的值则状态转移方程为dp[i] max(dp[j])1其中 0≤ji 且 num[j]num[i]。即考虑往 dp[0…i−1] 中最长的上升子序列后面再加一个 nums[i]。由于 dp[j] 代表 nums[0…j] 中以 nums[j] 结尾的最长上升子序列所以如果能从 dp[j] 这个状态转移过来那么 nums[i] 必然要大于 nums[j]才能将 nums[i] 放在 nums[j] 后面以形成更长的上升子序列。最后整个数组的最长上升子序列即所有 dp[i] 中的最大值。class Solution { public: int lengthOfLIS(vectorint nums) { int n (int)nums.size(); if (n 0) { return 0; } vectorint 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()); } };时间复杂度O(n^2)空间复杂度O(n)好了本文到这里就结束了希望认真阅读全文的小伙伴都能有所收获哦