C++ में अधिकतम लगातार 1 III

मान लीजिए हमारे पास 0 और 1 की एक सरणी A है, हम अधिकतम K मानों को 0 से 1 में अपडेट कर सकते हैं। हमें सबसे लंबे (सन्निकट) उपसरणी की लंबाई ढूंढनी है जिसमें केवल 1 हों। उदाहरण के लिए, यदि A = [1,1,1,0,0,0,1,1,1,1,0] और k = 2 है, तो आउटपुट 6 होगा। यदि हम 2 शून्य को फ्लिप करते हैं, तो सरणी [1,1,1,0,0,1,1,1,1,1,1] जैसी हो सकती है, 1 की सबसे लंबी अनुक्रम लंबाई 6 है।

हल करने के चरण

• ans := 0, j := 0 और n := सरणी का आकार सेट करें
• i को 0 से n-1 तक लूप करें
  • यदि A[i] 0 है, तो k को 1 से घटाएं
  • जब तक j <= i और k < 0
    • यदि A[j] = 0, तो k को 1 से बढ़ाएं
    • j को 1 से बढ़ाएं
  • ans := max(i - j + 1, ans)
• 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