Max Consecutive Ones II - Tìm dãy 1 liên tiếp dài nhất sau khi đảo tối đa một số 0

Cho một mảng nhị phân, tìm số lượng lớn nhất các số 1 liên tiếp nếu được phép đảo tối đa một số 0 thành 1.

Ví dụ: đầu vào [1,0,1,1,0], kết quả là 4 vì nếu đảo số 0 đầu tiên, ta được dãy 1 liên tiếp dài nhất là 4.

Giải thuật (Cửa sổ trượt)

Duyệt mảng với hai con trỏ i (phải) và j (trái). Đếm số lượng số 0 trong cửa sổ. Nếu số 0 > 1, thu hẹp cửa sổ từ trái. Cập nhật độ dài lớn nhất.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int ret = 1;
        int n = nums.size();
        if (!n) return 0;
        int j = 0;
        int zero = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) zero++;
            while (j <= i && zero > 1) {
                if (nums[j] == 0) zero--;
                j++;
            }
            ret = max(ret, i - j + 1);
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,0,1,1,1,0,1,1};
    cout << (ob.findMaxConsecutiveOnes(v));
    return 0;
}

Đầu vào

{1,0,1,1,1,0,1,1}

Đầu ra

6