[leetcode] number of maximum consecutive ones

leetcode Medium maximum continuous 1 A summary of several categories of topics .

Maximum continuous 1 The number of Ⅰ

1. Title Description

leetcode Topic link ：485. Maximum continuous 1 The number of

2. Thought analysis

Method 1 ： One traverse

encounter nums[i] == 1, be count++, encounter nums[i] == 0, be count=0, Then update the maximum continuous 1 The number of .

Method 2 ： Double pointer

Fixed left boundary , Then judge the right boundary , Update the difference between the maximum value and the right boundary minus the left boundary .

Method 3 ： Dynamic programming

dp[i] Says to the first i Maximum continuity at the end of elements 1 The number of .

among ： The double pointer method has the shortest running time .

3. Reference code

Method 1 ： One traverse

class Solution {
    
    public int findMaxConsecutiveOnes(int[] nums) {
    
        int res = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
    
            if (nums[i] == 1) {
    
                count++;
            } else {
    
                count = 0;
            }
            res = Math.max(res, count);
        }
        return res;
    }
}

Method 2 ： Double pointer

class Solution {
    
    public int findMaxConsecutiveOnes(int[] nums) {
    
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
    
            int j = i;
            while (j < nums.length && nums[j] == 1) {
    
                j++;
            }
            res = Math.max(res, j - i);
            i = j;
        }
        return res;
    }
}

Method 3 ： Dynamic programming

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

Maximum continuous 1 The number of Ⅱ

1. Title Description

leetcode Topic link ：Leetcode 487. Maximum continuous 1 The number of Ⅱ,plus Membership title , Look at the problem directly .

Given a binary array , You can at most 1 individual 0 Flip to 1, Find the largest one of them 1 The number of .

 Input ：[1,0,1,1,0]
 Output ：4
 explain ： Flip the first  0  You can get the longest continuous  1.
      When flipped , Maximum continuous  1  The number of  4.

2. Thought analysis

3. Reference code

class Solution {
    
    public int findMaxConsecutiveOnes(int[] nums) {
    
        int left = 0, right = 0;
        int res = 0, count = 0;
        while (right < nums.length) {
    
            if (nums[right++] == 0) {
    
                count++;
            }
            while (count > 1) {
    
                if (nums[left++] == 0) {
    
                    count--;
                }
            }
            res = Math.max(res, right - left);
        }
        return res;
    }
}

Maximum continuous 1 The number of Ⅲ

1. Title Description

leetcode Topic link ：1004. Maximum continuous 1 The number of III

2. Thought analysis

Maximum continuous 1 The number of Ⅱ An advanced version of , Yes k individual 0 Flip to 1.

3. Reference code