Subtask 1:

Ta có thể dùng 2 vòng lặp để thử từng cách (đoạn con) có thể thực hiện. Với mỗi đoạn con, ta sẽ xác định số con đen sau khi lật rồi đưa chúng vào một CTDL dạng set Số lượng hải cẩu đen sau khi lật một đoạn con bất kỳ có thể tính bằng cách lấy số lượng hải cẩu đen hiện tại cộng cho số lượng hải cẩu trắng trong đoạn (vì sau khi lật chúng sẽ thành đen) và trừ đi số lượng hải cẩu đen trong đoạn. Việc đếm số lượng con trắng và đen trên từng đoạn con sẽ mất thêm ~\mathcal{O}(N)~ chi phí, nhưng ta có thể thực hiện việc đếm này trong ~\mathcal{O}(1)~ bằng cách tạo trước 2 mảng tiền tố ~cnt_0~ và ~cnt_1~ để lưu số lượng con trắng và đen.

Độ phức tạp: ~\mathcal{O}(N^2 \cdot \log_2{N})~

Subtask 2:

Thay vì cố gắng xét tất cả các trường hợp có thể, ta sẽ tìm một cách đổi một đoạn con sao cho số con hải cẩu đen ~max~ là tối đa. Vì mỗi lần ta đổi một con đen thành trắng ta sẽ giảm số lượng con đen xuống và ngược lại, ta sẽ đánh giá trị lại các con đen lại thành ~-1~ và những con trắng thành ~1~. Tìm một cách đổi sao cho số con đen tối đa đồng nghĩa với tìm một đoạn có thể tăng nhiều con đen nhất, nên đây trở thành bài toán kinh điển tìm đoạn con có tổng lớn nhất trên đoạn đã đánh giá trị lại.

Việc tìm cách thay ~min~ có ít con hải cẩu đen nhất cũng có thể làm tương tự như trên. Nhận xét rằng số lượng số các con đen khác nhau chính là ~max - min + 1~, vì trước hết ta có thể đạt được nhiều nhất là ~max~ con đen và ít nhất là ~min~ con đen. Trong quá trình tính đoạn con có tổng lớn nhất, vì giá trị của dãy là ~1~ hoặc ~-1~ nên tổng của mình sẽ chỉ tăng hoặc giảm ~1~ đơn vị mỗi lần cập nhật. Do đó nếu tồn tại đoạn để tổng đạt ~max~ thì chắc chắn sẽ tồn tại đoạn có tổng đạt ~max - 1~, và nếu tồn tại đoạn có tổng đạt ~min~ thì cũng sẽ có đoạn đạt tổng ~min + 1~.

Độ phức tạp: ~\mathcal{O}(N)~.