LongestContinuousIncreasingSubsequence [source code]

public class LongestContinuousIncreasingSubsequence {
static
/******************************************************************************/
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int len = 0, prev = -1, res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > prev) {
                len++;
            } else {
                if (len > res)
                    res = len;
                len = 1;
            }
            prev = nums[i];
        }
        return Math.max (res, len);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        LongestContinuousIncreasingSubsequence.Solution tester = new LongestContinuousIncreasingSubsequence.Solution();
        int[][] inputs = {
            {1,3,5,4,7}, {3},
            {2,2,2,2,2}, {1},
            {1,3,5,7}, {4},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[] nums = inputs[2 * i];
            int ans = inputs[2 * i + 1][0];
            System.out.println (Printer.separator ());
            int output = tester.findLengthOfLCIS (nums);
            System.out.printf ("%s -> %s, expected: %d\n",
                Printer.array (nums), Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

读完题目感觉好像不是很难? 也许是我理解的太简单了? 刚开始还感觉是不是要用Stack来做, 后来想想好像Stack其实都是不必要的;

题目总体不难, 最后还是很快的做出来了, 被收尾问题稍微坑了一下(test3), 最后速度是5ms (60%);

之前认为需要重视收尾问题的是分段算法, 但是这里这个算法结果也需要注意收尾问题, 你有没有想过他们之间有什么共同点? 我认为, 需要注意收尾问题的一个关键类型, 就是这种switched update问题, 也就是对于res的update, 依赖于类似下降沿这样的东西的trigger才能发生. 这个时候, 往往需要考虑一下最后收尾结束的时候是不是需要人工的加一个trigger;

当然另外一个解决办法就是加一个dummy tail (在保证不影响最终结果的前提下), 这样就不用手动解决收尾问题了;

这个是editorial的解法:

Every (continuous) increasing subsequence is disjoint, and the boundary of each such subsequence occurs whenever nums[i-1] >= nums[i]. When it does, it marks the start of a new increasing subsequence at nums[i], and we store such i in the variable anchor.

For example, if nums = [7, 8, 9, 1, 2, 3], then anchor starts at 0 (nums[anchor] = 7) and gets set again to anchor = 3 (nums[anchor] = 1). Regardless of the value of anchor, we record a candidate answer of i - anchor + 1, the length of the subarray nums[anchor], nums[anchor+1], ..., nums[i]; and our answer gets updated appropriately.

class Solution {  
    public int findLengthOfLCIS(int[] nums) {  
        int ans = 0, anchor = 0;  
        for (int i = 0; i < nums.length; ++i) {  
            if (i > 0 && nums[i-1] >= nums[i]) anchor = i;  
            ans = Math.max(ans, i - anchor + 1);  
        }  
        return ans;  
    }  
}

这个人是@awice, 后来翻了一下, 这个人是一个很厉害的大神, contest排名全球第7;

他这个用anchor的思路很有意思; 不知道在其他的问题里面会不会有更多的应用; 我自己的这个做法, 是因为受Stack思路的影响比较厉害, 所以跟他这个有点区别, 不过这种类似anchor的对于分界点的敏感性, 好像在其他问题里面也见到过, 可以适当锻炼一下;

discussion里面类似我的思路的版本:

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

不维护prev, 直接就用access来查询历史, 这个不难理解;

为什么他这里不需要考虑收尾问题? 因为他这个算法的update, 其实不是switched的, 也就是说, 你看, 他res的update, 其实是在每次cnt进行update的时候, 都同时进行update的; 所以他最后不需要进行收尾; 反正各有优劣; 这种写法肯定是更加好理解一些;

关于这个取舍, 实际上这个作者自己也有一个说法:

@Vincent-Cai said in [Java/C++]Clean solution:

@mazong1123 Thanks for your suggestion! Actually, I have considered this possible improvement. But, we cannot assume that there are more increasing sequence than Non-increasing sequence, right? For example of [2,2,2,2,2], max runs just once. But, if I write max in else, then it will run 4 times. So I just try to make the code look clean..

感觉他说的是对的, 两种做法其实都是各有优劣, 就看实际给的input, 是switch多, 还是continuance多, 所以不好说哪种做法就绝对的更有优势;

注意他i == 0 || nums[i-1] < nums[i]这里的这个技巧: 用||来完成的一个short circuit来保护array access;

submission最优解其实只是波动, 最后都差不多;

Problem Description

Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).

Example 1:

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:

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.

Difficulty:Easy
Total Accepted:21.1K
Total Submissions:49.5K
Contributor:今が最高
Companies
facebook
Related Topics
array
Similar Questions
Number of Longest Increasing SubsequenceMinimum Window Subsequence