C++에서 하위 배열을 대칭 이동하여 0의 수 최대화

문제 설명

주어진 이진 배열에서 하위 배열을 한 번 뒤집을 수 있는 배열에서 최대 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. 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