\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-force>}}\)

• Thử từng đoạn và kiểm tra nếu thỏa thì cập nhật độ dài tối ưu

\(\color{orange}{\text{Hint 2 <Implementation>}}\)

• Ta duyệt qua từng phần tử \(x\) tại vị trí \(cur\)

Gọi \(cnt0\) là số lượng số 0 tính tới hiện tại

Gọi \(cnt1\) là số lượng số 1 tính tới hiện tại

Gọi \(diff = cnt0 - cnt1\) là độ chênh lệch tính tới hiện tại

Gọi \(f[l..r]\) là giá trị đô chênh trong khoảng \([l, r]\)

Ta dùng một mảng khác để lưu \(M[diff] = pos\) tức là vị trí nhỏ nhất để đạt đô chênh \(diff\) là vị trí \(pos\)

Nếu như mảng chưa lưu vị trí thì ta lưu vị trí đó

Nếu mảng đã lưu vị trí thì ta lấy khoảng từ \(M[diff] + 1 \rightarrow pos\)

Chứng minh: Có \(f[0..M[diff]] = f[0..cur] = diff \rightarrow f[M[diff] + 1..pos] = 0\)

\(\color{orange}{\text{Hint 2 <Binary-search>}}\)

\(\color{green}{\text{Preference AC Code }}\): STL, Hash, Implementation, Online Solving

\(^{^{\color{purple}{\text{Complexity : }} O(n)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int main()          
{
    int n = readInt();

    int cnt0 = 0;
    int cnt1 = 1;
    unordered_map<int, int> M;
    int res = 0;
    for (int i = 0; i < n; ++i)
    {
        bool x;
        cin >> x;
        if (x) cnt1++; else cnt0++;
        int diff = cnt0 - cnt1;

        if (M.count(diff))
            res = max(res, i - M[diff]);
        else        
            M[diff] = i;
    }
    cout << res;
    return 0;
}