codeforces 327A. Flipping Game

題目連結：http://www.codeforces.com/problemset/problem/327/A

題意：給定一個01序列，選擇一個連續的子段，對其翻轉(0變1，1變0)，然後對所有數求和，求最大值。

想法：由于n隻有100，是以 O(n3) 的暴力做法可以直接過，即枚舉子段的起點和終點。我們不妨考慮下更快速的做法，比如 O(n) 的做法。問題的實質在于求出一個子段，它的值最下，那麼一下子問題便化成我們熟悉的最大子段和問題了。我們對于每個0，它反轉後的貢獻為1，每個1的貢獻為-1。然後我們記dp[i]表示以i結尾的最大字段和，則dp[i] = max(d[i - 1], 0) + s[i]。那麼答案即為numberOfOne + max{dp[i]}。

代碼如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>

typedef long long ll;
const int MAXN =  + ;
int s[MAXN], dp[MAXN];

int main(){
    int n, ans = ;
    scanf("%d", &n);
    for(int i = ; i < n; ++i){
        int x;
        scanf("%d", &x);
        s[i] = x? - : ;
        if(x){
            ++ans;
        }
    }
    dp[] = s[];
    int mx = dp[];
    for(int i = ; i < n; ++i){
        dp[i] = std::max(dp[i - ], ) + s[i];
        mx = std::max(dp[i], mx);
    }
    printf("%d\n", ans + mx);
    return ;
}