Accept: 414 Submit: 1501
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
海边躺着一排咸鱼，一些有梦想的咸鱼成功翻身（然而没有什么卵用），一些则是继续当咸鱼。一个善良的渔夫想要帮这些咸鱼翻身，但是渔夫比较懒，所以只会从某只咸鱼开始，往一个方向，一只只咸鱼翻过去，翻转若干只后就转身离去，深藏功与名。更准确地说，渔夫会选择一个区间[L,R]，改变区间内所有咸鱼的状态，至少翻转一只咸鱼。
渔夫离开后想知道如果他采取最优策略，最多有多少只咸鱼成功翻身，但是咸鱼大概有十万条，所以这个问题就交给你了！
Input
包含多组测试数据。
每组测试数据的第一行为正整数n，表示咸鱼的数量。
第二行为长n的01串，0表示没有翻身，1表示成功翻身。
n≤100000
Output
在渔夫的操作后，成功翻身咸鱼（即1）的最大数量。
Sample Input
Sample Output
Hint
对于第一个样例，翻转区间[2,3]，序列变为1 1 1 1 0。
对于第二个样例，翻转整个区间，序列变为1 0 1。
Source
福州大学第十四届程序设计竞赛_重现赛标记为1的咸鱼翻过身来的话，咸鱼翻身数会减一。所以1的咸鱼标记为-1；
标记为0的咸鱼翻过身来的话，咸鱼数会加一。所以0的咸鱼标记为1；
那么这题就转换成，从总区区间内找一个连续区间使其区间和最大。这样，这题就转换成M子段最大和问题。
求M子段最大和问题的转移方程为 (M个子段不一定是连续的,但一定不相交)
dp【i】【j】 = max（dp【i】【j-1】，dp【i-1】【K】） + num【j】
这里来解释一下转移方程
dp【i】【j】代表前j个数分成i份时的最大值
当选择dp【i】【j-1】时代表第j个数加入第i个子段 这时最大值为 dp【i】【j-1】 + num【j】，相当于前j-1个数分成i份，然后第j个数加入第i段
当选择dp【i-1】【K】时代表第j个数自己成为第i个子段。此处K的取值为0<k<j 代表前K个数分成i-1段，然后第j个数自己构成第i段。此处的dp【i-1】【k】需要取dp【i-1】【1】~dp【i-1】【j-1】这个范围中的最大值
优化
但问题是如果要这样求的话，时间复杂度过高。为n^3。我们需要降低复杂度。
降低复杂度的最直接的方法是删去最大值计算的过程，我们可以看到dp【i-1】【k】保存的是i的上个状态i-1的最大值。那我们每次求i状态时都保存此状态下的最大值，这样就可以把复杂度降为n^2
但是这题只需要我们求M==1（一个子段）的情况 所以复杂度为O（n）
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
#define M(a,b) memset(a,b,sizeof(a))
const int MAXN = 1e5+5;
const int INF = 0x3f3f3f3f;
int n;
int fish[MAXN];
int num[MAXN];
int dp[MAXN];
int mx[MAXN];
int main()
{while(~scanf("%d",&n)){M(dp,0);M(mx,0);int sum = 0;for(int i=1; i<=n; i++){scanf("%d",&fish[i]);if(fish[i]==1) sum++;}if(sum == n){printf("%d\n",n-1);continue;}for(int i=1; i<=n; i++){if(fish[i]==1) num[i] = -1;///1的咸鱼标记为-1else num[i] = 1;///0的咸鱼标记为1}int MAX = -1*INF;for(int i=1; i<=n; i++){dp[i] = max(dp[i-1],mx[i-1])+num[i];mx[i-1] = MAX;MAX = max(dp[i],MAX);}printf("%d\n",MAX+sum);}return 0;
}