Description

Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.

Example 1:

Input: [1,0,1,1,0]
Output: 4

Explanation: Flip the first zero will get the the maximum number of consecutive 1s.
After flipping, the maximum number of consecutive 1s is 4.

Solution of dynamic programming

This problem is the variant of previous Max Consecutive Ones, only with one more limitation that we can flip one 1 to 0.

We can still use the dynamic programming method to solve it, but we need to distinguish the two states, flipped or non-flipped.

Suppose we define two arrays:

dp1[i] stands for non-flipped state, the max consecutive length end at position i.

dp2[i] stands for flipped state, the max consecutive length end at position i.

The trivial difference in the recurrence relation is we can not add one based on dp2[i-1], since we can only flip one 1 to 0.

But we can use dp1[i-1]+1, since we haven’t flipped ones in this state.

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int> &nums) {
        vector<int> dp1(nums.size());
        vector<int> dp2(nums.size());
        int ans = 0;
        for (int i = 0; i < nums.size(); i++){
            if (nums[i]) {
                dp1[i] = i >= 1 ? 1 : dp1[i - 1] + 1;
                dp2[i] = i >= 1 ? 1 : dp2[i - 1] + 1;
            }
            else {
                dp1[i] = 0;
                dp2[i] = i >= 1 ? 1 : dp1[i - 1] + 1;
            }
            ans = max(ans, dp2[i]);
        }
        return ans;
    }
};

An simpler solution

This problem is a special case of Max Consecutive Ones III. We can use the two-pointer approach to solve it.

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, zero = 0, left = 0, K = 1;
        for (int right = 0; right < nums.size(); ++right) {
            if (nums[right] == 0) 
                ++zero;
            while (zero > K) {
                if (nums[left++] == 0) --zero;
            }
            res = max(res, right - left + 1);
        }
        return res;
    }
};

Preparing for an interview? Check out this!