https://www.luogu.org/problem/P1115
和很久以前做的一個叫傳球游戲的一樣。。
題目描述
給出一段序列，選出其中連續(xù)且非空的一段使得這段和最大。

輸入格式
第一行是一個正整數(shù)N，表示了序列的長度。

第二行包含N個絕對值不大于10000的整數(shù)Ai ，描述了這段序列。

輸出格式
一個整數(shù)，為最大的子段和是多少。子段的最小長度為11。

輸入輸出樣例
輸入 #1 復(fù)制

7 2 -4 3 -1 2 -4 3

輸出 #1 復(fù)制

4

說明/提示
【樣例說明】

2,?4,3,?1,2,?4,3中，最大的子段和為4，該子段為3,?1,2.

【數(shù)據(jù)規(guī)模與約定】

對于40%的數(shù)據(jù)，有N≤2000。

對于100%的數(shù)據(jù)，有N≤200000。
/*
只需關(guān)注：
加上下一個數(shù)之前需不需要舍棄前面部分
*/

#include <bits/stdc++.h> using namespace std; const int maxn = 2e5+5; int a[maxn]; int main() {int n;cin>>n;for(int i = 0; i < n ; i++){cin>>a[i];}int sum = a[0],ans = sum;for(int i = 1; i < n; i++){int temp = sum + a[i];if(temp < a[i])//說明前面的sum為負(fù)，需要舍棄{sum = a[i];}else//前面sum為正，加上a[i]{sum = temp;}ans = max(ans,sum);}cout<<ans<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的P1115 最大子段和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。