张店免费做网站,企业标准备案平台官网,网络公司给销售公司做网站,凡科代理千万不要做#Java #动态规划
Feeling and experiences#xff1a;
最长递增子序列#xff1a;力扣题目链接
给你一个整数数组 nums #xff0c;找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不…#Java #动态规划
Feeling and experiences
最长递增子序列力扣题目链接
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1
输入nums [10,9,2,5,3,7,101,18]
输出4
解释最长递增子序列是 [2,3,7,101]因此长度为 4 。子序列的问题
定义dp数组dp数组的含义
到达第 i 个元素时最长的递增子序列为dp[i]
class Solution {public int lengthOfLIS(int[] nums) {if(nums.length 0){return 0;}int[] dp new int[nums.length];int res 1;Arrays.fill(dp, 1);for (int i 1; i dp.length; i) {for (int j 0; j i; j) {if (nums[i] nums[j]) {dp[i] Math.max(dp[i], dp[j] 1);}res Math.max(res, dp[i]);}}return res;}
}• 使用两层嵌套循环遍历数组其中外层循环控制当前元素的索引 i内层循环遍历之前的元素通过索引 j。
• 在内层循环中检查 nums[i] 是否大于之前的元素 nums[j]如果是说明可以将当前元素加入到以 nums[j] 结尾的递增子序列中。
• 更新 dp[i] 为当前值和以 nums[j] 结尾的子序列长度加1的较大者。
• 同时不断更新全局变量 res 为当前 dp[i] 和之前的 res 中的较大者。 这里用到的了 dp[j] 1是因为满足条件后要算上当前的这个数 来进行比较 最长连续递增序列力扣题目链接
给定一个未经排序的整数数组找到最长且 连续递增的子序列并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 rl r确定如果对于每个 l i r都有 nums[i] nums[i 1] 那么子序列 [nums[l], nums[l 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。 示例 1
输入nums [1,3,5,4,7]
输出3
解释最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的因为 5 和 7 在原数组里被 4 隔开。 先用贪心的思想简单又好理解
只要第 i 1 个元素 大于 第 i 个元素就使得计数 1否则 计数 重新置 1从头开始
class Solution {public int findLengthOfLCIS(int[] nums) {//先用贪心的方法来做//贪心思想只要 第 i1个元素比第 i 个元素大就使得 计数1否则从头开始int res 1;//记录结果int count 1; //计数//循环遍历for(int i 0;inums.length-1;i){//只要 满足if(nums[i1] nums[i]){count;}else{count 1;}if(count res){res count;}}return res;}
} 动态规划
但是感觉没有 贪心好理解 主要用于解决一系列问题
class Solution {public static int findLengthOfLCIS(int[] nums) {int[] dp new int[nums.length];Arrays.fill(dp, 1);int res 1;for (int i 1; i nums.length; i) {if (nums[i] nums[i - 1]) { dp[i] dp[i - 1] 1;}res res dp[i] ? res : dp[i];}return res;}
} 伤心桥下春波绿
曾是惊鸿照影来
Fighting
