674. 最长连续递增序列


674. 最长连续递增序列

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

class Solution &#123;
    public int findLengthOfLCIS(int[] nums) &#123;
    // 求数组nums中,最长的递增子数组的长度
        if (nums == null || nums.length == 0) return 0;
        int pre = 1; // pre表示dp[i-1]: 必须以i-1位置结尾的递增子数组长度
        int ans = 1;
        for (int i = 1; i < nums.length; i++) &#123;
            int cur = 1;
            if (nums[i] > nums[i-1]) cur += pre;
            ans = Math.max(ans, cur);
            pre = cur;///向下传递
        &#125;
        return ans;
    &#125;
&#125;

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

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

所以,定义 DP:

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

自己写的也 ok

class Solution &#123;
    public int findLengthOfLCIS(int[] nums) &#123;
    // 求数组nums中,最长的递增子数组的长度
        if (nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];// pre表示dp[i-1]: 必须以i-1位置结尾的递增子数组长度
        dp[0]=1;
        int ans = 1;
        for (int i = 1; i < nums.length; i++) &#123;
            if (nums[i] > nums[i-1]) dp[i] =dp[i-1]+1;
            else dp[i]=1;
            ans = Math.max(ans, dp[i]);//ok
        &#125;
        return ans;
        //return dp[nums.length-1];//这个为什么不行?
    &#125;
&#125;

文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
169. 多数元素 169. 多数元素
169. 多数元素难度简单给定一个大小为 n *的数组,找到其中的多数元素。多数元素是指在数组中出现次数 *大于** ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例  1:输入:[3,2,3]输出:3
下一篇 
104. 二叉树的最大深度 104. 二叉树的最大深度
104. 二叉树的最大深度难度简单 806给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例:给定二叉树 [3,9,20,null,null,15,7],   
  目录