7-2 最大子段和 (40 分)
给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。
要求算法的时间复杂度为O(n)。
输入格式:
输入有两行：
第一行是n值（1<=n<=10000)；
第二行是n个整数。
输出格式:
输出最大子段和。
输入样例:
在这里给出一组输入。例如：
6
-2 11 -4 13 -5 -2
输出样例:
在这里给出相应的输出。例如：
20
代码：
#include <iostream>
using namespace std;
int findMax(int a[],int n){
int sum = 0;
int b = 0;
for(int i = 0 ;i < n; i++){
if(b>0){
b =b + a[i];
}else{
b = a[i];
}
if(b>sum) sum=b;
}
return sum;
}
int main(){
int n;
cin>>n;
int a[10001];
for(int i=0;i<n;i++){
cin>>a[i];
}
cout<<findMax(a,n);
return 0;
}
解题思路：因为不要求字段是连续的，所以这题并不难，只需设置一个数和另一个数（max）并初始化为零，不断的从a[0]开始加，所得为负数则直接将数组的下一个数赋值给它，否则一直叠加，如果这个数大于max，则赋值给max。