通过翻转C ++中的子数组来最大化0

问题陈述

给定二进制数组，请在允许翻转子数组的情况下找到数组中的最大零个数。翻转操作将所有0切换为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