DP/Easy/CodeForces

#include <bits/stdc++.h>
using namespace std;


int main() {
    
    int n; cin>>n;
    vector<int> num(n);
    
    for(int i=0; i<n; i++){
        cin>>num[i];
    }
    
    
    vector<int> dp(n);
    
    vector<int> dp0(n);
    vector<int> dp1(n);
    
    if(n == 1){
        if(num[0] == 0){
            cout<<1;
            return 0;
        }
    }
    
    int c0 = 0;
    int c1 = 0;
    for(int i=0; i<n; i++){
        
        if(num[i] == 0){
            c0++;
        }else{
            c1++;
        }
        
        dp0[i] = c0;
        dp1[i] = c1;
        
    }
    
    int check = 0;
    for(int i=0; i<n; i++){
        if(num[i] == 1){
            check++;
        }
    }
    
    if(check == n){
        cout<<n-1;
        return 0;
    }
    
    int a = 0;
    int b = 0;
    
    int maxi = 0;
    for(int i=1; i<n; i++){
        for(int j=0; j<i; j++){
            int zero = dp0[i] - dp0[j];
            int one = dp1[i] - dp1[j];
            int next = dp0[i] - dp1[i];
            int total = zero - one;
            total = total < 0 ? 0 : total;
            next = next < 0 ? 0 : next;
            // cout<<total<<" ";
            if(maxi < next){
                maxi = next;
                a = 1;
                b = i+1;
            }
            if(maxi < total){
                maxi = total;
                a = j+2;
                b = i+1;
            }
        }
        dp[i] = maxi;
    }
    // cout<<endl;
    // cout<<a<<" "<<b<<endl;
    
    int ans = 0;
    for(int i=0; i<n; i++){
        if(i>=a-1 && i<=b-1){
            if(num[i] == 0){
                ans++;
            }
        }else{
            if(num[i] == 1){
                ans++;
            }
        }
    }
    
    cout<<ans;
   
}