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

समस्या कथन

एक बाइनरी सरणी को देखते हुए, एक सरणी में शून्य की अधिकतम संख्या ज्ञात करें जिसमें एक सबरे के एक फ्लिप की अनुमति है। एक फ्लिप ऑपरेशन सभी 0s से 1s और 1s से 0s तक स्विच करता है

अगर arr1={1, 1, 0, 0, 0, 0, 0}

यदि हम पहले 2 1 से 0 तक पलटते हैं, तो हम आकार 7 की उप-सरणी इस प्रकार प्राप्त कर सकते हैं -

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

एल्गोरिदम

1. Consider all subarrays and find a subarray with maximum value of (count of 1s) – (count of 0s)
2. Considers this value be maxDiff. Finally return count of zeros in original array + 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