Leetcode 674 最长连续递增序列

题意理解：

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

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

        这里的子序列，要求连续，所以当碰到不递增的情况断开。

        这里采用动态规划的思路来进行解题。

解题思路：

        （1）dp[i]表示到nums[i]符合递增要求的子序列的最大长度。

        （2）初始化

                每个数字开始，都能获得一个长度的递增子序列

                所以dp数组初始化为1

        （3）递推公式

                if(dp[i-1]<dp[i])

                        dp[i]=dp[i-1]+1

1.解题

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

2.分析

时间复杂度： O(n)

空间复杂度： O(n)