Java O(n) time O(1) space


  • 0
    W

    first, let us define CO list as a contiguous subarray of original array which satisfies that it has at least n - 1 ones (n is the length of the subarray)

    Then we have

    longest CO list = Max(longest CO list ending at index 0, longest CO list ending at index 1, ..., longest CO list ending at index m - 1)

    Also, we can define dp[i] = length of longest CO list ending at index i

    dp[i] = dp[i - 1] + 1 if (nums[i] == 1)
    dp[i] = i - j if (nums[i] == 0), where j is the zero position of CO list ending at index i - 1

    since dp[i] only depends on dp[i - 1], we only need to maintain two varaibles:

    1. curlen: the CO list length of last index;
    2. zeropos: 0 position in the CO list of last index (if it has no zero, set to -1)
    public int findMaxConsecutiveOnes(int[] nums) {
            
            if(nums.length == 0)return 0;
            
            int n = nums.length;
            
            int maxlen = 1;
            
            int curlen = 1;
            int zeropos = -1;
            
            if(nums[0] == 0)zeropos = 0;
            
            for(int i = 1; i < nums.length; i++)
            {
                if(nums[i] == 1)curlen++;
                else
                {
                    if(zeropos < 0)
                    {
                        curlen++;
                        zeropos = i;
                    }
                    else
                    {
                        curlen = i - zeropos;
                        zeropos = i;
                    }
                }
                
                if(curlen > maxlen)maxlen = curlen;
            }
            
            return maxlen;
            
            
            
            
        }
    

  • 0
    W
    This post is deleted!

Log in to reply
 

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