网站模板源码下载,网页设计作业总结,保护稀有动物网站建设策划书,做外贸找生意上哪个网站题意理解#xff1a; 给定一个未经排序的整数数组#xff0c;找到最长且 连续递增的子序列#xff0c;并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r#xff08;l r#xff09;确定#xff0c;如果对于每个 l i r#xff0c;都有 nums[i… 题意理解 给定一个未经排序的整数数组找到最长且 连续递增的子序列并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 rl r确定如果对于每个 l i r都有 nums[i] nums[i 1] 那么子序列 [nums[l], nums[l 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。 这里的子序列要求连续所以当碰到不递增的情况断开。 这里采用动态规划的思路来进行解题。 解题思路 1dp[i]表示到nums[i]符合递增要求的子序列的最大长度。 2初始化 每个数字开始都能获得一个长度的递增子序列 所以dp数组初始化为1 3递推公式 if(dp[i-1]dp[i]) dp[i]dp[i-1]1 1.解题
public int findLengthOfLCIS(int[] nums) {int[] dpnew int[nums.length];Arrays.fill(dp,1);for(int i1;i nums.length;i){if(nums[i-1]nums[i])dp[i]dp[i-1]1;}int max0;for(int i0;inums.length;i){maxMath.max(dp[i],max);}return max;}
2.分析 时间复杂度 O(n) 空间复杂度 O(n)
