网站栏目结构优化,网站开发有关费用,网站开发台州,网上有多少个购物平台目录
LeetCode674.最长连续递增序列
题目描述
解法1#xff1a;动态规划
代码实现 题目链接
题目描述
给定一个未经排序的整数数组#xff0c;找到最长且 连续递增的子序列#xff0c;并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r#xff08;l 动态规划
代码实现 题目链接
题目描述
给定一个未经排序的整数数组找到最长且 连续递增的子序列并返回该序列的长度。
连续递增的子序列 可以由两个下标 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 隔开。
示例 2 输入nums [2,2,2,2,2] 输出1 解释最长连续递增序列是 [2], 长度为1。
提示 0 nums.length 10^4 -10^9 nums[i] 10^9
解法1动态规划
这个题求连续的递增序列我们在遍历的过程中也可以使用dp数组将我们每一个位置的最长递增序列表示出来如果当前nums数组的值大于上一个位置的值那么看上一个dp[i-1]的值如果不为0则dp[i] dp[i-1] 1; 确定dp数组dp table以及下标的含义
dp[i]以下标i为结尾的连续递增的子序列长度为dp[i]。
注意这里的定义一定是以下标i为结尾并不是说一定以下标0为起始位置。 确定递推公式
如果 nums[i] nums[i - 1]那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 1 。
即dp[i] dp[i - 1] 1;
因为本题要求连续递增子序列所以就只要比较nums[i]与nums[i - 1]而不用去比较nums[j]与nums[i] j是在0到i之间遍历。 dp数组如何初始化
以下标i为结尾的连续递增的子序列长度最少也应该是1即就是nums[i]这一个元素。所以dp[i]应该初始1; 确定遍历顺序
从递推公式上可以看出 dp[i 1]依赖dp[i]所以一定是从前向后遍历。
本文在确定递推公式的时候也说明了为什么本题只需要一层for循环代码如下
for (int i 1; i nums.size(); i) {if (nums[i] nums[i - 1]) { // 连续记录dp[i] dp[i - 1] 1;}
}
代码实现
class Solution {public int findLengthOfLCIS(int[] nums) {int len nums.length;if (len 1) return 1;int max 0;int temp 1;for (int i 1; i len; i) {if (nums[i] nums[i-1]) {temp;}else {temp 1;}max Math.max(max,temp);}
return max;}
}
