[分治递归]解决最大子序列和问题

Pnig0s1992 p.s:比较直白简单的嵌套for循环顺序累加判断的方式就不介绍了，比较容易实现，而且时间复杂度O(N^3) or O(N^2)比较坑爹。这里用分治递归的方法去解决O(NlogN)，当然还有动态规划的方法O(N)以后再说。

先简单总结下分治递归的基本过程：

    1，传入待处理的序列集合，及初始下标(iLeft)和终点下标(iRight=N-1,N为元素个数)

    2，处理小容量问题 e.g:if(iLeft == iRight){....}

    3，将数据从中间分成两部分并将前后两部分依次递归调用。

    4，处理每个子段的过程。

核心部分注释的比较详细了，纯算法练习，高手飘过。

1. //Code By Pnig0s1992  
2. //Date:2012,3,12  
3. #include <stdio.h>  
4. #include <Windows.h>  
5. #include <stdlib.h>  
6.  
7. #define N 8  
8.  
9. int CallSubsequenceSum(int s[],int iLength);  
10. int SubsequenceSum(int s[],int iLeft,int iRight);  
11. int Maxinthree(int a,int b,int c);  
12.  
13. int main(int argc,CHAR * argv[])  
14. {  
15.     int myList[N] = {4,-3,5,-2,-1,2,6,-2};  
16.     int myResult;  
17.     for(int i=0;i<N;i++)  
18.     {  
19.         printf("%d ",myList[i]);  
20.     }  
21.     myResult = CallSubsequenceSum(myList,N-1);  
22.     printf("\n最大子序列和为:%d",myResult);  
23.     system("pause");  
24. }  
25.  
26. int CallSubsequenceSum(int s[],int iLength)  
27. {  
28.      return SubsequenceSum(s,0,iLength);  
29. }  
30.  
31. int SubsequenceSum(int s[],int iLeft,int iRight)  
32. {  
33.     int iMaxLeftSum,iMaxRightSum; //表示  
34.     int iRightBorderSum = 0,iLeftBorderSum = 0;  
35.     int iMaxLeftBorderSum = 0,iMaxRightBorderSum = 0;  
36.     int iCenter;  
37.     if(iLeft == iRight) //解决小容量情况，当序列只有一个元素时，非负则返回唯一值，否则返回0(基准情况)  
38.     {  
39.         if(s[iLeft]>0)  
40.         {  
41.             return s[iLeft];  
42.         }else 
43.         {  
44.             return 0;  
45.         }  
46.     }  
47.     iCenter = (iLeft+iRight)/2;  
48.     iMaxLeftSum = SubsequenceSum(s,iLeft,iCenter); //每次递归返回时，该值为该子段的最终左最大子序列和  
49.     iMaxRightSum = SubsequenceSum(s,iCenter+1,iRight); //每次递归返回时，该值为该子段的右最大自序列和  
50.     for(int i=iCenter;i>=iLeft;i--) //从中间向左扩展求子段的最大子序列和，必然包括子段的最右端数  
51.     {  
52.         iLeftBorderSum+=s[i];  
53.         if(iLeftBorderSum>iMaxLeftBorderSum)  
54.         {  
55.             iMaxLeftBorderSum = iLeftBorderSum; //包含左端数的最大子序列和  
56.         }  
57.     }  
58.     for(int j=iCenter+1;j<=iRight;j++) //从中间向右扩展求子段的最大子序列和，必然包括子段的最左端数  
59.     {  
60.         iRightBorderSum += s[j];  
61.         if(iRightBorderSum > iMaxRightBorderSum)  
62.         {  
63.             iMaxRightBorderSum = iRightBorderSum; //包含右端数的最大子序列和  
64.         }  
65.     }  
66.     //返回左子最大序列和，右最大子序列，及横跨中间的最大子序列和三者的最大值  
67.     return Maxinthree(iMaxLeftSum,iMaxRightSum,iMaxLeftBorderSum+iMaxRightBorderSum);   
68. }  
69.  
70. int Maxinthree(int a,int b,int c)  
71. {  
72.     if(b>a)  
73.         a=b;  
74.     if(a<c)  
75.         return c;  
76.     else 
77.         return a;  
78. } 

本文转hackfreer51CTO博客，原文链接：http://blog.51cto.com/pnig0s1992/803907，如需转载请自行联系原作者