在最大子序列的问题中，这里有四种解法，时间复杂度由高到低，可以直观的感受到解决问题的算法技巧。
c语言代码如下：
#include <stdio.h> #define maxn 100 int A[maxn]; //输入 void Input(int a[],int n) { int i; for(i=0;i<n;i++) scanf("%d",&a[i]); } //输出 void Output(int a[],int n) { int i; for(i=0;i<n;i++) printf("%d ",a[i]); } //O=(N*N*N) int MaxSubSequenceSum1(int a[],int n) { int ThisSum,MaxSum,i,j,k; MaxSum=0; 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*N） int MaxSubSequenceSum2(int a[],int n) { int ThisSum,MaxSum,i,j; MaxSum=0; 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) int MaxSubSequenceSum3(int a[],int x,int n) { int i,mind,left=x,right=n,LeftMax,RightMax,LeftBorder=0,RightBorder=0,MaxRight=0,MaxLeft=0; if(left==right) if(a[left]>0) return a[left]; else return 0; mind=(left+right)/2; LeftMax=MaxSubSequenceSum3(a,left,mind); RightMax= MaxSubSequenceSum3(a,mind+1,right); for(i=mind;i>=left;i--) { LeftBorder+=a[i]; if(LeftBorder>MaxLeft) MaxLeft=LeftBorder; } for(i=mind+1;i<right;i++) { RightBorder+=a[i]; if(RightBorder>MaxRight) MaxRight=RightBorder; } return (MaxRight+MaxLeft)>(RightMax>LeftMax?RightMax:LeftMax)?MaxRight+MaxLeft:(RightMax>LeftMax?RightMax:LeftMax); } //O=(N) int MaxSubSequenceSum4(int a[],int n) { int i,MaxSum=0,ThisSum=0; for(i=0;i<n;i++) { ThisSum+=a[i]; if(ThisSum>MaxSum) MaxSum=ThisSum; else if(ThisSum<0) ThisSum=0; } return MaxSum; } int main(int argc, char *argv[]) { int n; while(scanf("%d",&n)==1) { Input(A,n); // Output(A,n); printf("MaxSubSequenceSum1=%d\n",MaxSubSequenceSum1(A,n)); printf("MaxSubSequenceSum2=%d\n",MaxSubSequenceSum2(A,n)); printf("MaxSubSequenceSum3=%d\n",MaxSubSequenceSum3(A,0,n)); printf("MaxSubSequenceSum4=%d\n",MaxSubSequenceSum4(A,n)); } return 0; }