เพิ่มจำนวน 0 โดยการ Flip Subarray ใน C++

โจทย์

ได้รับ Binary Array หาจำนวน 0 สูงสุดในอาร์เรย์ด้วยการ Flip Subarray ได้ 1 ครั้ง Flip หมายถึงสลับ 0 เป็น 1 และ 1 เป็น 0

ถ้า arr1 = {1, 1, 0, 0, 0, 0, 0}

ถ้าเรา Flip 1 ตัวแรก 2 ตัวเป็น 0 จะได้ Subarray ขนาด 7 ดังนี้

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

อัลกอริทึม

1. พิจารณา Subarray ทุกอัน หา Subarray ที่มีค่า (จำนวน 1) - (จำนวน 0) สูงสุด
2. ให้ค่านี้เป็น maxDiff สุดท้ายคืน จำนวน 0 ในอาร์เรย์เดิม + maxDiff

ตัวอย่างโค้ด

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

int getMaxSubArray(int* arr, int n) {
    int maxDiff = 0;
    int zeroCnt = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] == 0) {
            ++zeroCnt;
        }
        int cnt0 = 0;
        int cnt1 = 0;
        for (int j = i; j < n; ++j) {
            if (arr[j] == 1) {
                ++cnt1;
            } else {
                ++cnt0;
            }
            maxDiff = max(maxDiff, cnt1 - cnt0);
        }
    }
    return zeroCnt + maxDiff;
}

int main() {
    int arr[] = {1, 1, 0, 0, 0, 0, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum subarray size = " << getMaxSubArray(arr, n) << endl;
    return 0;
}

ผลลัพธ์

Maximum subarray size = 7