मान लीजिए कि हमारे पास 0s और 1s की एक सरणी A है, हम 0 से 1 तक K मान तक अपडेट कर सकते हैं। हमें सबसे लंबे (सन्निहित) सबअरे की लंबाई का पता लगाना होगा जिसमें केवल 1s हो। तो अगर ए =[1,1,1,0,0,0,1,1,1,1,0] और के =2, तो आउटपुट 6 होगा, इसलिए यदि हम 2 0 फ्लिप करते हैं, तो सरणी हो सकती है [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