如何网站推广,知名的集团门户网站建设费用,信阳住房和城乡建设局网站,微网站与手机网站的区别300. 最长递增子序列https://leetcode.cn/problems/longest-increasing-subsequence/description/
给你一个整数数组nums#xff0c;找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不改变其…300. 最长递增子序列https://leetcode.cn/problems/longest-increasing-subsequence/description/
给你一个整数数组nums找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。
输入nums [10,9,2,5,3,7,101,18]输出4解释最长递增子序列是[2,3,7,101]因此长度为4。输入nums [0,1,0,3,2,3]输出4。输入nums [7,7,7,7,7,7,7]输出1。
提示1 nums.length 2500-10^4 nums[i] 10^4。
进阶你能将算法的时间复杂度降低到O(nlog(n))吗 我们用动态规划的思想来解决这个问题。
确定状态表示根据经验和题目要求我们用dp[i]表示以i位置为结尾的所有子序列中最长递增子序列的长度。
推导状态转移方程以i位置为结尾的所有子序列分为2类长度为1的子序列长度大于1的子序列。如果子序列的长度是1那么这个子序列是递增子序列。下面我们考虑长度大于1的子序列。
如果以i位置为结尾的子序列的长度大于1我们可以继续细分为i位置元素的前面是i - 1位置元素的子序列i位置元素的前面是i - 2位置元素的子序列i位置元素的前面是i - 3位置元素的子序列……i位置元素的前面是0位置元素的子序列。也就是说如果子序列中i位置元素的前面是j位置元素那么j的范围是[0, i - 1]。
对于每一个j如果nums[j] nums[i]那么这个子序列就有可能是递增子序列。要想这个子序列尽可能得长就要找到以j位置为结尾的最长递增子序列在这个子序列后面添加nums[i]即为以i位置为结尾的最长递增子序列。
综上所述dp[i]应该取「1」和「所有满足0 j i并且nums[j] nums[i]的j中最大的dp[j]加1」的较大值。
所以我们可以把dp表的值都初始化为1其中dp[0] 1是显然的。如果i 0那么dp[i]就应该取所有满足0 j i并且nums[j] nums[i]的j中最大的dp[j]加1。
填表顺序根据状态转移方程显然应从左往右填表。
返回值根据状态表示应返回dp表的最大值。
细节问题dp表的规模和nums相同均为1 x n。
class Solution {
public:int lengthOfLIS(vectorint nums) {int n nums.size();// 创建dp表vectorint dp(n, 1);// 填表for (int i 1; i n; i) {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());}
};
