C++ में अधिकतम लगातार 1s II - एक 0 को फ्लिप करने की अनुमति

समस्या विवरण

मान लीजिए हमारे पास एक बाइनरी सरणी है; हमें इस सरणी में अधिकतम लगातार 1s की संख्या ढूंढनी है यदि हम अधिकतम एक 0 को फ्लिप कर सकते हैं।

उदाहरण के लिए, यदि इनपुट [1,0,1,1,0] है, तो आउटपुट 4 होगा क्योंकि यदि हम पहले 0 को फ्लिप करते हैं तो हमें अधिकतम लगातार 1s मिलते हैं। फ्लिप करने के बाद, अधिकतम लगातार 1s की संख्या 4 होगी।

समाधान दृष्टिकोण

इस समस्या को स्लाइडिंग विंडो तकनीक का उपयोग करके हल किया जा सकता है:

दो पॉइंटर्स (i और j) का उपयोग करके एक विंडो बनाएं
विंडो में अधिकतम एक 0 होने दें
जब विंडो में एक से अधिक 0 हो जाएं, तो बाएं पॉइंटर (j) को दाएं बढ़ाएं
प्रत्येक चरण पर अधिकतम विंडो आकार को ट्रैक करें

एल्गोरिदम चरण

ret := 1, n := nums का आकार
यदि n शून्य है, तो 0 लौटाएं
j := 0, zero := 0
i को 0 से n-1 तक लूप करें:
- यदि nums[i] == 0, तो zero बढ़ाएं
- जब (j <= i और zero > 1) हो:
  - यदि nums[j] == 0, तो zero घटाएं
  - j बढ़ाएं
- ret = max(ret, i - j + 1) अपडेट करें
ret लौटाएं

C++ कार्यान्वयन

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int findMaxConsecutiveOnes(vector<int>& nums) { 
        int ret = 1; 
        int n = nums.size(); 
        if (!n) 
            return 0; 
        int j = 0; 
        int zero = 0; 
        for (int i = 0; i < n; i++) { 
            if (nums[i] == 0) { 
                zero++; 
            } 
            while (j <= i && zero > 1) { 
                if (nums[j] == 0) { 
                    zero--; 
                } 
                j++; 
            } 
            ret = max(ret, i - j + 1); 
        } 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {1,0,1,1,1,0,1,1}; 
    cout << (ob.findMaxConsecutiveOnes(v)); 
    return 0;
}

इनपुट

{1,0,1,1,1,0,1,1}