题目:
给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。
连续递增的子序列 可以由两个下标 l
和 r
(l < 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;}