Tối đa hóa số bit 0 bằng cách lật một mảng con trong C++

Đề bài

Cho mảng nhị phân (chỉ chứa 0 và 1). Được phép chọn một mảng con liên tiếp và lật tất cả bit (0→1, 1→0). Tìm số lượng 0 lớn nhất có thể đạt được.

Ví dụ: {1,1,0,0,0,0,0} → lật 2 phần tử đầu (1→0) → toàn bộ thành 0 → 7 số 0.

Thuật toán (Biến đổi thành bài toán Maximum Subarray Sum)

Lật mảng con → số 0 tăng thêm = (số 1 trong mảng con) - (số 0 trong mảng con).

Gán trọng số: 1 → +1, 0 → -1. Tìm mảng con có tổng lớn nhất (Kadane). Kết quả = số 0 gốc + maxSubarraySum.

Ví dụ minh họa (C++)

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

int getMaxSubArray(int* arr, int n) {
    int zeroCnt = 0;
    for (int i = 0; i < n; ++i) if (arr[i] == 0) ++zeroCnt;

    int maxDiff = 0, curr = 0;
    for (int i = 0; i < n; ++i) {
        int val = (arr[i] == 1) ? 1 : -1;
        curr = max(val, curr + val);
        maxDiff = max(maxDiff, curr);
    }
    return zeroCnt + maxDiff;
}

int main() {
    int arr[] = {1, 1, 0, 0, 0, 0, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "So 0 toi da = " << getMaxSubArray(arr, n) << endl;
    return 0;
}

Kết quả

So 0 toi da = 7

Lưu ý: Code gốc dùng O(n²), phiên bản trên tối ưu O(n) bằng Kadane.