C++ में सबएरे फ्लिप करके 0 की संख्या को अधिकतम करना

समस्या कथन

एक बाइनरी ऐरे दिया गया है, एक सबएरे के एक फ्लिप की अनुमति के साथ ऐरे में अधिकतम शून्य की संख्या ढूंढें। एक फ्लिप ऑपरेशन सभी 0 को 1 में और 1 को 0 में बदल देता है।

यदि arr1 = {1, 1, 0, 0, 0, 0, 0}

यदि हम पहले 2 1 को 0 में फ्लिप करते हैं, तो हम आकार 7 का सबएरे प्राप्त कर सकते हैं:

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

एल्गोरिदम

1. सभी सबएरे पर विचार करें और (1 की गिनती) - (0 की गिनती) के अधिकतम मान वाला सबएरे ढूंढें।
2. इस मान को maxDiff मानें। अंत में मूल ऐरे में शून्य की गिनती + 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