当前位置: 首页> 娱乐> 明星 > 动态规划---最长连续递增序列

动态规划---最长连续递增序列

时间:2025/7/16 2:31:07来源:https://blog.csdn.net/m0_65096633/article/details/142250402 浏览次数:0次

题目:

给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。

连续递增的子序列 可以由两个下标 lrl < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

思路:

1.确定dp数组及含义

dp[i]代表i及i之前最长连续递增序列的长度

2.确定递推公式

如果nums[i]>nums[i-1],那么有dp[i]=dp[i-1]+1

3.初始化dp数组

所有元素初始化为1

4.确定遍历顺序

从小到大遍历

代码:

    public int findLengthOfLCIS(int[] nums) {int length=nums.length;int[] dp=new int[length];Arrays.fill(dp,1);int result=1;for(int i=1;i<length;i++){if(nums[i]>nums[i-1])dp[i]=dp[i-1]+1;if(dp[i]>result) result=dp[i];}return result;}

关键字:动态规划---最长连续递增序列

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: