请教个问题,关于最大子序列求和问题
程序代码:
//Code By Pnig0s1992 //Date:2012,3,12 #include <stdio.h> #include <Windows.h> #include <stdlib.h> #define N 8 int CallSubsequenceSum(int s[],int iLength); int SubsequenceSum(int s[],int iLeft,int iRight); int Maxinthree(int a,int b,int c); int main(int argc,CHAR * argv[]) { int myList[N] = {4,-3,5,-2,-1,2,6,-2}; int myResult; for(int i=0;i<N;i++) { printf("%d ",myList[i]); } myResult = CallSubsequenceSum(myList,N-1); printf("\n最大子序列和为:%d",myResult); system("pause"); } int CallSubsequenceSum(int s[],int iLength) { return SubsequenceSum(s,0,iLength); } int SubsequenceSum(int s[],int iLeft,int iRight) { int iMaxLeftSum,iMaxRightSum; //表示 int iRightBorderSum = 0,iLeftBorderSum = 0; int iMaxLeftBorderSum = 0,iMaxRightBorderSum = 0; int iCenter; if(iLeft == iRight) //解决小容量情况,当序列只有一个元素时,非负则返回唯一值,否则返回0(基准情况) { if(s[iLeft]>0) { return s[iLeft]; }else { return 0; } } iCenter = (iLeft+iRight)/2; iMaxLeftSum = SubsequenceSum(s,iLeft,iCenter); //每次递归返回时,该值为该子段的最终左最大子序列和 ? iMaxRightSum = SubsequenceSum(s,iCenter+1,iRight); //每次递归返回时,该值为该子段的右最大自序列和 ? for(int i=iCenter;i>=iLeft;i--) //从中间向左扩展求子段的最大子序列和,必然包括子段的最右端数 { iLeftBorderSum+=s[i]; if(iLeftBorderSum>iMaxLeftBorderSum) { iMaxLeftBorderSum = iLeftBorderSum; //包含左端数的最大子序列和 ? } } for(int j=iCenter+1;j<=iRight;j++) //从中间向右扩展求子段的最大子序列和,必然包括子段的最左端数 { iRightBorderSum += s[j]; if(iRightBorderSum > iMaxRightBorderSum) { iMaxRightBorderSum = iRightBorderSum; //包含右端数的最大子序列和 ? } } //返回左子最大序列和,右最大子序列,及横跨中间的最大子序列和三者的最大值 return Maxinthree(iMaxLeftSum,iMaxRightSum,iMaxLeftBorderSum+iMaxRightBorderSum); } int Maxinthree(int a,int b,int c) { if(b>a) a=b; if(a<c) return c; else return a; }
打问号的是没弄懂的地方,分别是第48、49行的递归为什么能实现左边、右边的最大子序列,为什么我觉得是左边第一个元素,右边的第一个元素。
还有第55行、63行,为什么包含了左端数、右端数的最大子序列和,我觉得if语句一用,就把最大子序列给存起来了,并不包含两端的数啊。
[此贴子已经被作者于2015-12-15 18:42编辑过]