C++でのMaxConsecutiveOnes III

0と1の配列Aがあるとすると、0から1までの最大K個の値を更新できます。1のみを含む最長の（連続した）サブ配列の長さを見つける必要があります。したがって、A=[1,1,1,0,0,0,1,1,1,1,0]およびk=2の場合、出力は6になります。したがって、2 0を反転すると、配列は次のようになります。 [1,1,1,0,0,1,1,1,1,1,1]のように、1の最長シーケンスの長さは6です。

これを解決するには、次の手順に従います-

• ans：=0、j：=0、n：=配列のサイズを設定
• 0からn–1の範囲のiの場合
  • A [i]が0の場合、kを1減らします
  • while j<=iおよびk<0
    • A [j] =0の場合、kを1増やします
    • jを1増やします
  • ans：=最大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