题目描述
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。
输入描述
输入共 2 行 第一行 一个正整数 n，代表序列的长度 第二行 n个整数，表示序列内的 n个整数
数据范围
0<n<=105
−10^7<=a[i]<=10^7
输出描述
输出一个整数，表示数组中最大的子段和
输入样例
1
9
-2 1 -3 4 -1 2 1 -5 4
2
7
2 -4 3 -1 2 -4 3
3
5
-2 -5 -19 -6 -3
输出样例
1
6
2
4
3
0
思路
数组-21-3……
最大子段和
第 i 项的最大子段和 = 前 i-1 项的最大子段和 + 第 i 项 或 第 i 项的最大子段和 = 第 i 项
代码
#include <iostream>
using namespace std
;
int n
,a
;
int maxn
=0,maxx
;
int main(){
int i
;
cin
>>n
;
cin
>>a
;
maxx
=a
;
for(i
=0;i
<n
-1;i
++){
cin
>>a
;
if(maxx
+a
>a
) maxx
+=a
;
else maxx
=a
;
if(maxx
>maxn
) maxn
=maxx
;
}
cout
<<maxn
;
return 0;
}
bye bye~
蒟蒻发声：有dalao有更好的方法吗？
