思路分析:
得到測試數(shù)據(jù)后a[ ]:[1 0 0 1 0] 求出原本1的數(shù) k=2
將其翻轉(zhuǎn)為b[ ]:[-1 1 1 -1 1] 求出最大區(qū)間連續(xù)和m=2
最終答案為 k+m
最大區(qū)間連續(xù)和的標準算法(不唯一):
采用動態(tài)規(guī)劃,只需要掃描一遍數(shù)組
dp[i]=max{0,dp[i-1]} + b[i]
// 求 b[ ]的最大區(qū)間連續(xù)和
temp = b[1]; m=0;
for (int i = 1; i <= n ;++ )
{
temp= max(0,temp)+a[i];
m = max(m,temp);
}
#include<iostream>
#include<algorithm>
using namespace std;
#define LOCAL
int main(){
#ifdef LOCAL
FILE *fin;
fin = freopen("FZU2253.txt", "r", stdin);
#endif
int n;
while(cin>>n){
int *a=new int[n+1];
int *b=new int[n+1]; //翻轉(zhuǎn)函數(shù)
int m=0,k=0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]){
k++;
b[i]=-1;
}
else b[i]=1;
}
if(m==n){//特判
cout<<n-1<<endl;
continue;
}
int temp=b[1];
for(int i=1;i<=n;i++){//求b最大區(qū)間連續(xù)和
temp=max(0,temp)+b[i];
m=max(m,temp);
}
cout<<m+k<<endl;
}
}