[Java/C++]Clean solution


  • 16

    The idea is to use cnt to record the length of the current continuous increasing subsequence which ends with nums[i], and use res to record the maximum cnt.

    Java version:

        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;
        }
    

    C++ version:

        int findLengthOfLCIS(vector<int>& nums) {
            int res = 0, cnt = 0;
            for(int i = 0; i < nums.size(); i++){
                if(i == 0 || nums[i-1] < nums[i]) res = max(res, ++cnt);
                else cnt = 1;
            }
            return res;
        }
    

  • 0

    Hope your advice!


  • 1

    @Hao-Cai For "very clean" I'd expect a few more space characters.


  • 0
    S
    This post is deleted!

  • 0

    @ManuelP Sorry... I have changed the title...


  • 0
    M

    It's clean but the performance can be improved because res = max(res, ++cnt) should not be executed everytime in the loop. It should be called only when:

    1. A new sequence started. E.G your "else".
    2. After the loop.

    max can hurt the performance really.


  • 1

    @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..


  • 0
    I

    Hi,

    Thanks for sharing code. When the following array is input to your code, it gives longest subsequence output as 7.
    [1, 5, 9, 13, 15, 17, 16, 18, 19, 21, 23, 25, 27, 20]

    If you see then in the above mentioned array, the longest subsequence is from digit 19 till 27 with a difference of 2 between each element. This sums up to 5 characters. Based on it, your answer is wrong.

    Though when this array is input on LeetCode editor to test the code, it shows 7 as result for the above mentioned array which I believe is also wrong output. How does the provided array accumulate to 7 continuous longest subsequence?

    Thanks,
    Sal


  • 1
    N

    @iprep said in [Java/C++]Clean solution:

    [1, 5, 9, 13, 15, 17, 16, 18, 19, 21, 23, 25, 27, 20]
    The longest increasing subsequence is from 16 to 27 which is of length 7.


  • 0
    I

    Thanks for the explanation. I got it. I thought that only difference between two consecutive numbers should be similar in longest subsequence. Got it and can modify my already existing algo accordingly.


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

    fixed the performance problem


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.