1049 最大子段和
N個整數組成的序列a[1],a[2],a[3],…,a[n],求該序列如a[i]+a[i+1]+…+a[j]的連續子段和的最大值。當所給的整數均為負數時和為0。
例如:-2,11,-4,13,-5,-2,和最大的子段為:11,-4,13。和為20。
收起
輸入
第1行:整數序列的長度N(2 <= N <= 50000)
第2 - N + 1行:N個整數(-10^9 <= A[i] <= 10^9)
輸出
輸出最大子段和。
輸入樣例
6
-2
11
-4
13
-5
-2
輸出樣例
20
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[10100011],n,mx,dp[101001];
int main() {
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
dp[i]=max(dp[i-1]+a[i],(ll)0);
mx=max(mx,dp[i]);
}
cout<<mx;
}