categories: [Blog,Algorithm]

674. 最长连续递增序列

难度简单172
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < 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。

  1. class Solution {
  2.     public int findLengthOfLCIS(int[] nums) {
  3.     // 求数组nums中，最长的递增子数组的长度
  4.         if (nums == null || nums.length == 0) return 0;
  5.         int pre = 1; // pre表示dp[i-1]: 必须以i-1位置结尾的递增子数组长度
  6.         int ans = 1;
  7.         for (int i = 1; i < nums.length; i++) {
  8.             int cur = 1;
  9.             if (nums[i] > nums[i-1]) cur += pre;
  10.             ans = Math.max(ans, cur);
  11.             pre = cur;///向下传递
  12.         }
  13.         return ans;
  14.     }
  15. }

这不就是一个简单的动态规划吗
问题：求数组nums中，最长递增子数组的长度。
子数组问题，一般常用套路：

  1. 子数组必须以 i 位置结尾时的答案是啥；
  2. 如果每个位置都能结算一个答案，最终的答案必是其中的max。

所以，定义DP：

  1. dp[i]含义：必须以 i 位置结尾的子数组中，最长递增子数组的长度是多少。
  2. dp[i] = nums[i] > nums[i-1] ? dp[i-1] + 1 : 1;
  3. ans = max { dp[i] }

自己写的也ok

  1. class Solution {
  2.     public int findLengthOfLCIS(int[] nums) {
  3.     // 求数组nums中，最长的递增子数组的长度
  4.         if (nums == null || nums.length == 0) return 0;
  5.         int[] dp = new int[nums.length];// pre表示dp[i-1]: 必须以i-1位置结尾的递增子数组长度
  6.         dp[0]=1;
  7.         int ans = 1;
  8.         for (int i = 1; i < nums.length; i++) {
  9.             if (nums[i] > nums[i-1]) dp[i] =dp[i-1]+1;
  10.             else dp[i]=1;
  11.             ans = Math.max(ans, dp[i]);//ok
  12.         }
  13.         return ans;
  14.         //return dp[nums.length-1];//这个为什么不行？
  15.     }
  16. }