最大子段和算法_头歌求序列-2 11 -4 13 -5 -2的最大子段和

给定由n个整数组成的系列a1,a2,a3,...,an,求该序列的子段和的最大值。当所以整数均为负整数时定义最大子段和为0。
例如序列[-2,11,-4,13,-5,-2]的最大子段和为20.

#include <stdlib.h> int LSS_Enumerate(const int a[],int count) { int i; int j; int iMax = a[0]; int sum[10000]; sum[0] = 0; for(i = 1; i <= count ;i++) { sum[i] = sum[i-1] + a[i-1]; //sum[i]代表了序列从1到i的和 } for(i = 0; i < count ;i++) { for (j = i; j < count ;j++) { //如果要算i到j的和，只需将sum[j]减去sum[i-1]即可 if ((sum[j+1] - sum[i]) > iMax) { iMax = sum[j+1] - sum[i]; } } } return iMax; } int main(int argc, char* argv[]) { int a[] = {-2,11,-4,13,-5,-2}; int ret = LSS_Enumerate(a,6); printf("LSS_Enumerate = %d/n",ret); system("pause"); return 0; }