三种最大子序列和问题解法
#include<stdio.h> int MaxsubseqSum4(int A[],int N); int MaxsubseqSum1(int B[],int n); //最大子列和 int main() { int a[8]={-1,3,-2,4,-6,1,6,-1}; int k,i; k=8; k=MaxsubseqSum4(a,k); printf("%d",k); k=MaxsubseqSum1(a,k); printf("%d",k); return 0; } int MaxsubseqSum4(int A[],int k) //最优解法，只用一层循环，从第一个开始小于零丢弃，只遍历一次就能得出最大子序列和。 { int Maxsum,thissum; int i; thissum=0; Maxsum=0; for(i=0;i<k;i++) { thissum+=A[i]; if(thissum>Maxsum) Maxsum=thissum; else if(thissum<0) thissum=0; } printf("%d",Maxsum); return Maxsum; } int MaxsubseqSum1(int B[],int k) { int ThisSum,Maxsum=0; //三层嵌套for循环 时间复杂度n^3。 很麻烦。 先从0加到最后 再从1加到最后 。。。。如果i=1，j=3 那么 thissum=a1+a2+a3 j=4 重复（a1+a2+a3）+a4
int i,j,l; for(i=0;i<k;i++) { for(j=i;j<k;j++) for(l=i;l<j;l++)//第三次 { ThisSum+=B[l]; if(ThisSum>Maxsum) Maxsum=ThisSum; // } } return Maxsum; } int MaxsubseqSum2(int B[],int k) //递推 { int thissum,maxsum=0; int j,i; for(i=0;i<k;i++) { thissum=0; for(j=i;j<k;j++) { thissum+=B[j]; // 3 -5 8 -7 6 //递推将上面的进行了优化 Sum（i，j）=sum(i,j-1)+aj 通过这个公式，减少了一层for循环。
if(thissum>maxsum) // maxsum=thissum; } } }
