最大子序列和问题

 1 int MaxSubsequenceSum (const int A[], int N)
 2 {
 3     int ThisSum, MaxSum = 0; 
 4     
 5     for(int i = 0; i != N; ++i)
 6         for(int j = i; j != N; ++j){
 7             ThisSum = 0;
 8             for(int k = i; k != j; ++k)
 9                 ThisSum += A[k];
10             if(MaxSum < ThisSum)
11                 MaxSum = ThisSum;
12         }
13     return MaxSum;
14 }

 1 int MaxSubsequenceSum (const int A[], int N)
 2 {
 3     int ThisSum, MaxSum = 0; 
 4     
 5     for(int i = 0; i != N; ++i){ 
 6         ThisSum = 0;
 7         for(int j = i; j != N; ++j){
 8             ThisSum += A[j];
 9             if(MaxSum < ThisSum)
10                 MaxSum = ThisSum;
11         }
12     }
13     return MaxSum;
14 }

 1 int Max3(int a, int b, int c)
 2 {
 3     int max;
 4     max = a > b ? a : b;
 5     max = max > c ? max : c;
 6     
 7     return max; 
 8 }
 9 
10 static int MaxSubSum (const int A[], int Left, int Right)    //Left左边界(0)   Right右边界(N-1) 
11 {
12     int MaxLeftSum, MaxRightSum;
13     int MaxLeftBorderSum, MaxRightBorderSum;
14     int LeftBorderSum, RightBorderSum;
15     int Mid;
16     
17     if(Left == Right)
18         if(A[Left] > 0)
19             return A[Left];
20         else
21             return 0;
22     
23     Mid = (Left + Right) / 2;
24     MaxLeftSum = MaxSubSum(A, Left, Mid);          //左侧递归
25     MaxRightSum = MaxSubSum(A, Mid+1, Right);      //右侧递归 
26     
27     MaxLeftBorderSum = 0; LeftBorderSum = 0;       //相比于第二种算法，去掉一个循环，每次分一半来求解最大值 
28     for(int i = Mid; i != Left-1; --i){
29         LeftBorderSum += A[i];
30         if(LeftBorderSum > MaxLeftBorderSum)
31             MaxLeftBorderSum = LeftBorderSum;
32     }
33     
34     MaxRightBorderSum = 0; RightBorderSum = 0;
35     for(int i = Mid+1; i != Right+1; ++i){
36         RightBorderSum += A[i];
37         if(RightBorderSum > MaxRightBorderSum)
38             MaxRightBorderSum = RightBorderSum;
39     }
40     
41     return Max3(RightBorderSum, MaxRightSum,        // 比较左侧最大值，右侧最大值和左右相加最大值 
42             MaxLeftBorderSum+MaxRightBorderSum);
43 }

 1 int MaxSubsequenceSum (const int A[], int N)
 2 {
 3     int ThisSum, MaxSum;
 4     ThisSum = MaxSum = 0; 
 5     
 6     for(int i = 0; i != N; ++i){ 
 7         ThisSum += A[i];
 8         if(MaxSum < ThisSum)
 9             MaxSum = ThisSum;
10         else if(ThisSum < 0)
11             ThisSum = 0;
12     }
13     return MaxSum;
14 }