(最大区间连续和)FZU-2553 Staly Fish 咸鱼问题

思路分析:

得到测试数据后a[ ]:[1 0 0 1 0] 求出原本1的数 k=2
将其翻转为b[ ]:[-1 1 1 -1 1] 求出最大区间连续和m=2
最终答案为 k+m

最大区间连续和的标准算法(不唯一):

采用动态规划,只需要扫描一遍数组
dp[i]=max{0,dp[i-1]} + b[i]

// 求 b[ ]的最大区间连续和
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]; //翻转函数 
    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最大区间连续和 
        temp=max(0,temp)+b[i];
        m=max(m,temp);
    }
    cout<<m+k<<endl;
    
}
    
}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。