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

Tuyên bố vấn đề

Cho một mảng nhị phân, hãy tìm số lượng số không tối đa trong một mảng với một lần lật mảng con được phép. Thao tác lật chuyển tất cả 0s thành 1s và 1s thành 0s

Nếu arr1 ={1, 1, 0, 0, 0, 0, 0}

Nếu chúng ta lật 2 chữ 1 đầu tiên thành 0, thì chúng ta có thể nhận được mảng con có kích thước 7 như sau -

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

Thuật toán

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.

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau−

Maximum subarray size = 7