বাইনারি অ্যারে A এবং পূর্ণসংখ্যা K দেওয়া। সর্বোচ্চ K টি ০কে ১-এ ফ্লিপ করে সবচেয়ে লম্বা ১-ओনলি সাবঅ্যারে বের করতে হবে।
উদাহরণ: A=[1,1,1,0,0,0,1,1,1,1,0], k=2 → ৬ (২টি ০ ফ্লিপ করে ৬টি ১)。」
সমাধানের ধাপসমূহ
- স্লাইডিং উইন্ডো:
iরাইট পয়েন্টার,jলেফট পয়েন্টার। kটি ০ অনুমোদন। ০ পেলেk--।k < 0হলেjবাড়িয়ে উইন্ডো সঙ্কুচিত করুন (০ পেলেk++)।- প্রতিটি ধাপে
ans = max(ans, i-j+1)।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestOnes(vector<int>& A, int k) {
int ans = 0, j = 0, 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(ans, i - j + 1);
}
return ans;
}
};
int main() {
vector<int> v = {1,1,1,0,0,0,1,1,1,1,0};
Solution ob;
cout << ob.longestOnes(v, 3); // output 10
}
ইনপুট
[1,1,1,0,0,0,1,1,1,1,0] 3
আউটপুট
10
