int MaxSubsequenceSum(const int A[],int N) { int thisSum=0,MaxSum=0,j; for(j=0;j<N;j++) { thisSum+=A[j]; printf("thisSum %d..A[%d]=%d\n",thisSum,j,A[j]); if(thisSum>MaxSum) { MaxSum=thisSum; printf("MaxSum:%d\n",MaxSum); } else if(thisSum<0) thisSum=0; } return MaxSum; } int main() { int number[]={1,-1,3,4}; int maxsum=0; printf("start ....\n"); maxsum=MaxSubsequenceSum(number,4); printf("maxsum:%d\n",maxsum); exit(0); }
运行得出结果
start .... thisSum 1..A[0]=1 MaxSum:1 thisSum 0..A[1]=-1 thisSum 3..A[2]=3 MaxSum:3 thisSum 7..A[3]=4 MaxSum:7 maxsum:7
此算法的优点，它只对数据进行一次扫描，一旦A[j]被读入并处理，它就不再需要被记忆。在于它可以被顺序读入，在主存中不必存储数组任何部分，在任何时刻，算法都能对它已经读入的数据给出子序列问题的正确答案。
