洛谷P1115： https://www.luogu.com.cn/problem/P1115
本題是想求出給定序列的最大子序列和，根據題意，可以從第一個數開始遍歷，每次將此數a[i],與此數與之前保留的和的和（a[i]+b[i]-1）比較取較大值，
再將b[i]與所保存最大值ans比較，從而求解，
開始做題時因為此題是在前綴和的題單中，所以一直把想法局限在利用前綴和求解，利用前綴和固然能求出，但翻閱題解后，發現此方法更加精妙，代碼更加簡化易懂，
詳見代碼如下：
#include<bits/stdc++.h>
using namespace std;
int n,a[200020],b[200020],i,ans;
int main(){
cin>>n;
for(i = 1;i <= n;i++){
cin>>a[i];
if(i < 2) b[i] = a[i];
else b[i] = max(a[i],b[i-1]+a[i]);
if(i < 2) ans = b[i];
ans = max(ans , b[i]);
}
cout<<ans;
return 0;
}
如有錯誤 敬請指正 ~~
大家多多點關注哦~~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/245278.html
標籤：其他