分治算法求解序列最大子和问题

 1 #include <stdio.h>
 2 
 3 int caluMaxSubSum(int *array, int left, int right);
 4 
 5 int main()
 6 {   
 7     int array[6] = {2, -2, 3, 1, -4, 2};
 8     int len_array = sizeof(array)/sizeof(array[0]);
 9     int i = 0;
10     int subsum = caluMaxSubSum(array, 0, len_array);
11     for(i = 0; i < len_array; i++)
12     {
13        printf("%d ", array[i]);
14     }
15     
16     printf("\n");
17     //printf("最大子和是: ");
18     printf("subsum = %d\n", subsum);    
19     return 0;
20 }
21 
22 int caluMaxSubSum(int *array, int left, int right)
23 {   
24    int sum = 0;
25    if(left >= right)
26    {
27       if(array[left] > 0)
28       {
29           sum  = array[left];
30       }
31       else
32       {   
33           sum = 0;  
34       }
35    }
36    else
37    {
38       int center = (left + right)/2;
39       int s1 = 0, s2 = 0;
40       int lefts = 0, rights = 0;
41       int i = 0;
42       int leftsum = caluMaxSubSum(array, left, center);
43       int rightsum = caluMaxSubSum(array, center + 1, right);
44       for(i = center; i >= left; i--)
45       {
46          lefts += array[i];
47          if(lefts > s1)
48          {
49              s1 = lefts;
50          }
51       }
52       
53       for(i = center + 1; i < right; i++)
54       {
55           rights += array[i];
56           if(rights > s2)
57           {
58              s2 = rights;
59           }          
60       }
61       
62       sum = s1 + s2;
63       if(sum < leftsum)
64       {
65          sum = leftsum;
66       }
67       if(sum < rightsum)
68       {
69           sum = rightsum;
70       }
71    }
72    
73    return sum;
74 }