Bài 11.2. Dãy Con Cân Bằng - [Độ khó: Khá]

Mô tả bài tập: Bạn là một nhà nghiên cứu dữ liệu, đang phân tích một chuỗi các sự kiện được đánh số. Mỗi sự kiện có thể được phân loại là "loại A" (nếu mã sự kiện là số chẵn) hoặc "loại B" (nếu mã sự kiện là số lẻ). Bạn muốn tìm ra khoảng thời gian dài nhất (dãy con liên tiếp) mà trong đó số lượng sự kiện loại A bằng số lượng sự kiện loại B. Nếu không có dãy con nào như vậy (ngoại trừ dãy con rỗng), kết quả là 0.

INPUT FORMAT Dòng đầu tiên chứa một số nguyên N (1 <= N <= 10^5) là số lượng sự kiện. Dòng thứ hai chứa N số nguyên e_1, e_2, ..., e_N (1 <= e_i <= 10^9) là các mã sự kiện.

OUTPUT FORMAT In ra một số nguyên duy nhất là độ dài của dãy con cân bằng dài nhất.

Ví dụ: Input:

8
1 2 3 4 5 6 7 8

Output:

8

Giải thích:

• Mảng sự kiện là [1, 2, 3, 4, 5, 6, 7, 8].
• Ta chuyển đổi mảng này thành một mảng mới để dễ dàng tính toán: gán 1 cho số chẵn và -1 cho số lẻ. Mục tiêu là tìm dãy con có tổng bằng 0 dài nhất.
  • 1 (lẻ) -> -1
  • 2 (chẵn) -> 1
  • 3 (lẻ) -> -1
  • 4 (chẵn) -> 1
  • 5 (lẻ) -> -1
  • 6 (chẵn) -> 1
  • 7 (lẻ) -> -1
  • 8 (chẵn) -> 1
• Mảng mới: [-1, 1, -1, 1, -1, 1, -1, 1]
• Các dãy con có tổng bằng 0:
  • [-1, 1] (tổng 0, độ dài 2)
  • [-1, 1, -1, 1] (tổng 0, độ dài 4)
  • ...
  • Toàn bộ mảng [-1, 1, -1, 1, -1, 1, -1, 1] có tổng bằng 0, độ dài 8.
• Độ dài lớn nhất là 8.

Ví dụ 2: Input:

5
2 4 6 8 10

Output:

0

Giải thích:

• Mảng sự kiện là [2, 4, 6, 8, 10].
• Chuyển đổi thành mảng mới: [1, 1, 1, 1, 1] (tất cả đều là số chẵn).
• Không có bất kỳ dãy con nào mà số lượng số chẵn bằng số lượng số lẻ (vì không có số lẻ nào). Tổng của bất kỳ dãy con nào cũng luôn dương. Do đó, không có dãy con nào có tổng bằng 0.
• Kết quả là 0.