leetcode674. 最长连续递增序列

1.题目描述：

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。连续递增的子序列可以由两个下标l和r（l < r）确定，如果对于每个l <= i < r，都有nums[i] < nums[i + 1]，那么子序列[nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]就是连续递增子序列。

2.贪心算法：很容易想到。

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if (nums.length == 1) return 1;
        int count = 1;
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) count++;
            else {
                max = Math.max(max, count);
                count = 1;//一旦不递增则将count置为1
            }
        }
        return Math.max(max, count);//本身是递增则取count
    }
}

3.动态规划： 

dp[i]代表以i索引位置结尾最长的连续递增序列。

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if(nums.length == 1) return 1;
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int max = 1;
        for (int i = 1; i < dp.length; i++) {
            if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;//连续递增则加一
            else dp[i] = 1;//建议直接放在dp数组的初始化
            max = Math.max(max, dp[i]); 
        }
        return max;
    }
}