最大子列和问题
//O(N^3) int MaxSubseqSum1(int A[],int N){ int ThisSum,MaxSum = 0; int i,j,k; for(i=0;i<N;i++){ for(j=i;j<N;j++) ThisSum = 0; for(k=i;k<=j;k++) ThisSum += A[k]; if(ThisSum > MaxSum){ MaxSum = ThisSum; } } return MaxSum; } //O(N^2) int MaxSubseqSum2(int A[],int N){ int ThisSum,MaxSum = 0; int i,j,k; for(i=0;i<N;i++){ ThisSum = 0; for(j=i;j<N;j++) ThisSum += A[j]; if(ThisSum > MaxSum){ MaxSum = ThisSum; } } return MaxSum; } //O(N*logN)——分治 //O(N)——在线处理 int MaxSubseqSum4(int A[],int N){ int ThisSum,MaxSum; int i; ThisSum = MaxSum = 0; for(i = 0;i<N;i++){ ThisSum += A[i]; if(ThisSum>MaxSum) MaxSum = ThisSum; else if(ThisSum<0) ThisSum = 0; } return MaxSum; }
原文:https://www.cnblogs.com/cxc1357/p/10610243.html