int MaxSubsequenceSum(const int A[],int N) { int thisSum,MaxSum,i,j,k; MaxSum=0; for(i=1;i<N;i++) { for(j=i;j<N;j++) { thisSum=0; for(k=i;k<j;j++) { thisSum+=A[K]; } if(thisSum>MaxSum) MaxSum=thisSum; } return MaxSum } }
举个例子,在test.c中:
#include <stdio.h> #include <stdlib.h> int MaxSubsequenceSum(const int A[],int N) { int thisSum,MaxSum,i,j,k; MaxSum=0; for(i=0;i<N;i++) { printf("i:%d ....\n",i); for(j=i;j<N;j++) { printf("j:%d ....\n",j); thisSum=0; for(k=i;k<=j;k++) { printf("k:%d ....\n",k); thisSum+=A[k]; } if(thisSum>MaxSum) MaxSum=thisSum; } } 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); }
linux下编译运行
gcc -o sub maxsub.c ./sub
得出结果
start .... i:0 .... j:0 .... k:0 .... j:1 .... k:0 .... k:1 .... j:2 .... k:0 .... k:1 .... k:2 .... j:3 .... k:0 .... k:1 .... k:2 .... k:3 .... i:1 .... j:1 .... k:1 .... j:2 .... k:1 .... k:2 .... j:3 .... k:1 .... k:2 .... k:3 .... i:2 .... j:2 .... k:2 .... j:3 .... k:2 .... k:3 .... i:3 .... j:3 .... k:3 .... maxsum:7
第一个for循环为N,第二个for循环大小为N-i;第三个for循环大小j-i+1;总数为O(1*N*N*N)=O()