C++-এ Max Consecutive Ones II: এক শূন্য ফ্লিপ করে সর্বোচ্চ সতত ১ খুঁজে বের করা

একটি বাইনারি অ্যারে দেওয়া আছে। আমাদের কাজ হলো সেটিতে সর্বোচ্চ কতগুলো সতত ১ থাকতে পারে যদি আমরা সtevilোopot একটি ০ কে ১ এ ফ্লিপ (পরিবর্তন) করতে পারি।

উদাহরণ

ইনপুট: [1,0,1,1,0]

আউটপুট: 4

ব্যাখ্যা: প্রথম ০ কে ১ এ ফ্লিপ করলে আমরা পাই [1,1,1,1,0] যেখানে সর্বোচ্চ ৪টি সতত ১ রয়েছে।

সমাধানের পদ্ধতি (Sliding Window / Two Pointers)

এই সমস্যাটি স্লাইডিং উইন্ডো বা টু পয়েন্টার টেকনিক দিয়ে দক্ষতার সাথে সমাধান করা যায়। ধাপগুলো:

ret = 1, n = nums.size() আরম্ভ করুন।
যদি n == 0 হয়, তবে 0 রিটার্ন করুন।
j = 0 (উইন্ডোর শুরু), zero = 0 (উইন্ডোতে থাকা শূন্যের সংখ্যা) আরম্ভ করুন।
i = 0 থেকে n-1 পর্যন্ত লুপ চালান:
- যদি nums[i] == 0 হয়, তবে zero++ করুন।
- যদি zero > 1 হয়, তবে উইন্ডোর শুরু j কে ডান দিকে সরান যতক্ষণ না zero <= 1 হয়। এই সময় যদি nums[j] == 0 হয়, তবে zero-- করুন।
- 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}