Số liên tiếp tối đa III trong C ++

Giả sử chúng ta có một mảng A gồm 0s và 1s, chúng ta có thể cập nhật tối đa K giá trị từ 0 đến 1. Chúng ta phải tìm độ dài của mảng con dài nhất (liền kề) chỉ chứa 1s. Vì vậy, nếu A =[1,1,1.0,0,0,1,1,1,1,0] và k =2, thì đầu ra sẽ là 6, Vì vậy, nếu chúng ta lật 2 số 0, mảng có thể là giống như [1,1,1,0,0,1,1,1,1,1,1], độ dài của chuỗi 1s dài nhất là 6.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• đặt ans:=0, j:=0 và n:=kích thước của mảng
• cho tôi trong phạm vi từ 0 đến n - 1
  • nếu A [i] bằng 0, thì giảm k đi 1
  • while j <=i và k <0
    • nếu A [j] =0, thì tăng k thêm 1
    • tăng j lên 1
  • ans:=max of i - j + 1, ans
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[1,1,1,0,0,0,1,1,1,1,0]
3

Đầu ra

10