GuilinDev

Lc0674

05 August 2008

674 Longest Continuous Increasing Subsequence

题目

Given an unsorted array of integers, find the length of longest 

1

continuous
increasing subsequence (subarray).

Example 1:

1
2
3
4

Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. 
Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4.

Example 2:

1
2
3

Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1.

Note: Length of the array will not exceed 10,000.

分析

这道题可以按直观做，但拿来练习DP非常不错。

1） 状态定义 - dp[i] - 到i位置时最长的上升子序列

2） 初始化 dp[0] = 1, dp[i]初始化都是1

3） 转移方程 dp[i] = dp[i - 1] + 1 if nums[i] > nums[i - 1]

1

                       = 1 if nums\[i\] <= nums\[i - 1\]

4） 考虑状态压缩，可以

代码

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    // dp[i] - 到i位置时最长的上升子序列
    // dp[0] = 1, 所以dp[i]初始化都是1
    // dp[i] = dp[i - 1] + 1 if nums[i] > nums[i - 1]
    //       = 1 if nums[i] <= nums[i - 1]
    public int findLengthOfLCIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        
        for (int i = 1; i < len; i++) {
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
        }
        
        //遍历每个位置，找到最大值，这步可以在前面的for循环中完成
        int result = 0;
        for (int m : dp) {
            result = Math.max(result, m);
        }
        
        return result;
    }
}

状态压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int maxL = 1; // 最大长度
        int prev = 1; // 前一个状态
        int curr = 1; // 当前状态
        
        for (int i = 1; i < len; i++) {
            if (nums[i] > nums[i - 1]) {
                curr = prev + 1;
                maxL = Math.max(maxL, curr);
                prev = curr;
            } else {// 重新开始计算
                curr = 1;
                prev = 1; 
            }
        }
        return maxL;
    }
}

直观做法，类似状态压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int res = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i == 0 || nums[i-1] < nums[i]) {//不是第一位，找到前面和现在的关系
                count++;
                res = Math.max(res, count);
            } else {
                count = 1;
            }
        }
        return res;
    }
}
This site is open source. Improve this page.