题目描述

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

示例 1:

输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。
示例 2:

输入: [2,2,2,2,2]
输出: 1
解释: 最长连续递增序列是 [2], 长度为1。

注意：数组长度不会超过10000。

算法

(动态规划) O(n)

步骤一:确定状态
       最长连续上升序列，一定是以某个元素nums[j] (j<=i)为结尾，但是不一定是当前这位置nums[i]。
       分两种情况:
       1. nums[j]一个就是组成最长连续上升序列，之前是下降的序列。
       2. nums[j-1] < nums[j],所以问题可以看子问题求以某个元素nums[j-1]为结尾的长度 + 1

       状态: dp[i] 取得以nums[i]为结尾的最长连续上升序列长度

步骤二:确定转移方程
       dp[i] = 1 (nums[i-1] >= nums[i])  or  dp[i-1] + 1 (nums[i-1] < nums[i])


步骤三:确定初始状态/边界状态
       dp数组初始值都为 = 1

步骤四:计算顺序遍历计算dp[0], dp[1], dp[2]...dp[n - 1]

Java 代码

public class Solution {

    public static int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        if (n == 0 || n == 1) {
            return n;
        }

        int res = 1;
        //  以下标i结尾的的最长上升序列个数
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = 1;
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = 1;
            }
            res = Math.max(res, dp[i]);
        }

        return res;
    }
}