Mảng con lớn nhất với số lượng 0 và 1 bằng nhau trong C ++

Hãy xem các bước để hoàn thành chương trình.

• Khởi tạo mảng.
• Chuyển tất cả các số 0 trong mảng thành -1.
• Có một bản đồ một bản đồ trống để lưu trữ các chỉ mục trước đó.
• Tổng khởi tạo thành 0, độ dài tối đa thành 0 và chỉ mục kết thúc thành -1.
• Viết một vòng lặp lặp lại cho đến n.
  • Thêm phần tử hiện tại vào tổng.
  • Nếu tổng bằng 0.
    • Cập nhật độ dài tối đa với i + 1.
    • Và kết thúc chỉ mục thành i.
  • Nếu tổng xuất hiện trong bản đồ tổng trước đó và i - beforeIndexes [sum] lớn hơn độ dài tối đa.
    • Cập nhật độ dài tối đa và chỉ mục kết thúc.
  • Nếu không, hãy thêm tổng vào bản đồ chỉ mục trước đó.
• In chỉ mục bắt đầu endIndex - maxLength + 1 và chỉ mục kết thúc endIndex.

Ví dụ

Hãy xem mã.

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

Đầu ra

Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.

1 8

Kết luận

Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.