LeetCode - 674. Longest Continuous Increasing Subsequence

Question

题目

求最长连续递增子串 (不是子序列)。

解析

比 最长递增子序列 更简单，同样提供三种解法。

一维 dp

class Solution {
    
    public int findLengthOfLCIS(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        int res = 1;
        int[] dp = new int[nums.length];
        dp[0] = 1;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > nums[i-1])
                dp[i] = dp[i-1] + 1;
            else 
                dp[i] = 1;
            res = Math.max(res, dp[i]); 
        }
        return res;
    }

}

记忆化递归：

class Solution {   
    
    public int res;
    public int findLengthOfLCIS(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, -1);
        res = 1;
        process(nums, nums.length-1, dp);
        return res;
    }
    public int process(int[] nums, int i, int[] dp){
        if(i == 0)
            return 1;
        if(dp[i] != -1)
            return dp[i];
        if(nums[i] > nums[i-1]){
            dp[i] = process(nums, i-1, dp) + 1;
        }else {
            dp[i] = 1;
            process(nums, i-1, dp); // still should 
        }
        res = Math.max(res, dp[i]);
        return dp[i];
    }
}

滚动优化

class Solution {   

    public int findLengthOfLCIS(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        int res = 1, cur = 1;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > nums[i-1])
                cur += 1;
            else 
                cur = 1;
            res = Math.max(res, cur); 
        }
        return res;
    }
}