学步园

思路：

　　计算出任意i到j之间连续子数组的和再比较必然能得到最大值，但时间复杂度为O（n^2），我们希望能找出线性时间的算法。

      我们注意到，假如数组中全为正数，那么最大和必然为全部数相加；如果数组中有负数，并且如果加上某个负数，子数组的和小于0，则最大和子数组必然不包含这个负数。 基于此，给出以下代码：

#include <stdio.h>
int getMaxSum(int a[],int m){
	int max=a[0];
	int sum=0,k;
	for(k=0;k<m;k++){
		if(sum < 0){
			sum=a[k];
		}
		else{
			sum+=a[k];
		}
		if(sum>max){
			max=sum;
		}
	}
	return max;
}
void main(){
	int a[]={1, -2, 3, 10, -4, 7, 2, -5};
	int max=getMaxSum(a,8);
	printf("%d",max);
}