E - Binary Inversions.cpp

#include <bits/stdc++.h>

using namespace std;

const int MX = 2e5 + 5;

int t, n, arr[MX], zeros[MX], ones[MX];

int main(){
    cin.tie(nullptr), ios::sync_with_stdio(false);
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 1; i <= n; i++){
            cin >> arr[i];
            zeros[i] = zeros[i - 1] + (1 - arr[i]);
            ones[i] = ones[i - 1] + arr[i];
        }

        long long int cnt = 0;
        int ans = 0;
        for(int i = 1; i <= n; i++){
            if(arr[i] == 1) cnt += zeros[n] - zeros[i];
        }

        for(int i = 1; i <= n; i++){
            if(arr[i] == 0){
                int num = zeros[n] - zeros[i] - ones[i];
                ans = max(ans, num);
            }else{
                int num = ones[i - 1] - zeros[n] + zeros[i];
                ans = max(ans, num);
            }
        }

        cout << (cnt + ans) << "\n";
    }
}