ধরুন আমাদের 0s এবং 1s এর একটি অ্যারে আছে, আমরা 0 থেকে 1 পর্যন্ত K মান পর্যন্ত আপডেট করতে পারি। আমাদের সবচেয়ে দীর্ঘতম (সংলগ্ন) সাবয়ারের দৈর্ঘ্য খুঁজে বের করতে হবে যেটিতে শুধুমাত্র 1s রয়েছে। সুতরাং যদি A =[1,1,1,0,0,0,1,1,1,1,0] এবং k =2, তাহলে আউটপুট হবে 6, তাই যদি আমরা 2 0s ফ্লিপ করি, তাহলে অ্যারে হতে পারে যেমন [1,1,1,0,0,1,1,1,1,1,1], 1s এর দীর্ঘতম অনুক্রমের দৈর্ঘ্য হল 6।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- উত্তর সেট করুন :=0, j :=0 এবং n :=অ্যারের আকার
- আমি 0 থেকে n – 1
- পরিসরে
- যদি A[i] 0 হয়, তাহলে k কে 1 কমিয়ে দিন
- যখন j <=i এবং k <0
- যদি A[j] =0 হয়, তাহলে k কে 1 দ্বারা বাড়ান
- j 1 দ্বারা বাড়ান
- উত্তর :=i – j + 1 এর সর্বোচ্চ, ans
- উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestOnes(vector<int>& A, int k) {
int ans = 0;
int j = 0;
int n = A.size();
for(int i = 0; i < n; i++){
if(A[i] == 0) k--;
while(j <= i && k <0){
if(A[j] == 0){
k++;
}
j++;
}
ans = max(i - j + 1, ans);
}
return ans;
}
};
main(){
vector<int> v = {1,1,1,0,0,0,1,1,1,1,0};
Solution ob;
cout <<(ob.longestOnes(v, 3));
} ইনপুট
[1,1,1,0,0,0,1,1,1,1,0] 3
আউটপুট
10
