(最大區(qū)間連續(xù)和)FZU-2553 Staly Fish 咸魚問題

思路分析:

得到測試數(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;
    
}
    
}

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點,簡書系信息發(fā)布平臺,僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容