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

Cho mảng nhị phân A và số k. Có thể đổi tối đa k số 0 thành 1. Tìm độ dài đoạn con liên tiếp toàn số 1 dài nhất.

Ví dụ: A = [1,1,1,0,0,0,1,1,1,1,0], k = 2 → 6.

Thuật toán giải quyết (Cửa sổ trượt)

1. Hai con trỏ j = 0, ans = 0.
2. Duyệt i = 0 .. n-1:
   • Nếu A[i] == 0 → k--.
   • Trong khi k < 0: nếu A[j] == 0 → k++; j++.
   • ans = max(ans, i - j + 1).
3. Trả về ans.

Ví dụ minh họa (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);
}

Đầu vào

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

Đầu ra

10