C++에서 0과 1의 수가 같은 가장 큰 부분배열

프로그램을 완료하는 단계를 살펴보겠습니다.

• 배열을 초기화합니다.
• 배열의 모든 0을 -1로 만듭니다.
• 이전 색인을 저장할 지도를 빈 지도로 만드세요.
• 합계를 0으로, 최대 길이를 0으로, 끝 인덱스를 -1로 초기화합니다.
• n이 될 때까지 반복하는 루프를 작성합니다.
  • 현재 요소를 합계에 추가합니다.
  • 합계가 0인 경우.
    • i + 1로 최대 길이를 업데이트합니다.
    • 그리고 종료 인덱스는 i.
  • 이전 합계 맵에 합계가 존재하고 i - previousIndexes[sum]이 최대 길이보다 큰 경우.
    • 최대 길이 및 끝 색인 업데이트
  • 그렇지 않으면 이전 인덱스 맵에 합계를 추가합니다.
• 시작 인덱스 endIndex - maxLength + 1 및 끝 인덱스 끝 인덱스를 인쇄합니다.

예시

코드를 봅시다.

#include <bits/stdc++.h>
using namespace std;
void findTheSubArray(int arr[], int n) {
   unordered_map<int, int> previousIndexes;
   int sum = 0, maxLength = 0, endingIndex = -1;
   for (int i = 0; i < n; i++) {
      arr[i] = arr[i] == 0 ? -1 : 1;
   }
   for (int i = 0; i < n; i++) {
      sum += arr[i];
      if (sum == 0) {
         maxLength = i + 1;
         endingIndex = i;
      }
      if (previousIndexes.find(sum) != previousIndexes.end()) {
         if (maxLength < i - previousIndexes[sum]) {
            maxLength = i - previousIndexes[sum];
            endingIndex = i;
         }
      }else {
         previousIndexes[sum] = i;
      }
   }
   cout << endingIndex - maxLength + 1 << " " << endingIndex << endl;
}
int main() {
   int arr[] = { 1, 1, 0, 0, 0, 1, 1, 1, 0 };
   findTheSubArray(arr, 9);
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

1 8

결론

튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.