487. number of maximum consecutive 1 II ●●

487. Maximum continuous 1 The number of II ●●

describe

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

Example

 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.

Answer key

1. Dynamic programming

1. dp[i][0] Express Subscript i-1 At the end , The longest continuous... Without a substitute operation 1 length ;
   dp[i][1] Express Subscript i-1 At the end , The longest continuous... With a substitution operation 1 length ;
2. Initialize to 0;
3. When nums[i-1] == 1：
   continuity 1 Without interruption ,dp[i][0] = dp[i-1][0] + 1;,dp[i][1] = dp[i-1][1] + 1;
   When nums[i-1] == 0：
   Without replacement , continuity 1 interrupt ,dp[i][0] = 0; ;
   If you choose to replace , Is transferred from the unreplaced array + 1dp[i][1] = dp[i-1][0] + 1;
4. Traversing from front to back .

greedy ： The continuous length of the operation used must be larger .

• Time complexity ：$O(N)$
• Spatial complexity ：$O(N)$, You can optimize with a one-dimensional rolling array

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int findMaxConsecutiveOnes(vector<int>& nums){
    
    int n = nums.size();
    int ans = 0;
    vector<vector<int>> dp(n+1, vector<int>(2, 0));
    for(int i = 1; i <= n; ++i){
    
        if(nums[i-1] == 1){
                     // dp[i]  Corresponding  nums[i-1]
            dp[i][0] = dp[i-1][0] + 1;      //  Not replaced 
            dp[i][1] = dp[i-1][1] + 1;      //  Replaced 
        }else{
    
            dp[i][0] = 0;                   //  Do not replace , continuity 1 interrupt 
            dp[i][1] = dp[i-1][0] + 1;      //  Transfer... From an array that has never been replaced  + 1
        }
        ans = max(ans, dp[i][1]);           //  greedy ： The continuous length of the operation used must be larger 
    }
    return ans;
}

int main(){
    
    vector<int> nums = {
    1, 0, 1, 1, 0};
    cout << findMaxConsecutiveOnes(nums);
    return 0;
}

2. The sliding window - Double pointer

In the statistics window 0 The number of , Greater than 1 when , Move the left pointer , Then determine the window size .

Reference resources 1004. Maximum continuous 1 The number of III ●●

• Time complexity ：$O(N)$
• Spatial complexity ：$O(1)$

int findMaxConsecutiveOnes2(vector<int>& nums){
    
    int n = nums.size();
    int ans = 0, l = 0, zero = 0;
    for(int r = 0; r < n; ++r){
    
        if(nums[r] == 0) ++zero;		//  Statistics  0  The number of 
        while(zero > 1){
    			
            if(nums[l] == 0) --zero;	//  Move the left pointer to the right 
            ++l;
        }
        ans = max(ans, r-l+1);
    }
    return ans;
}