算法第二章上机实践报告

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int MaxSum(int a[],int left,int right)
 5 {
 6     int maxsum = 0;
 7     
 8     //递归的变界条件
 9     if(left == right){
10         if(a[left] > 0){
11             return a[left];
12         }
13         else{
14             return 0; //如果序列中所有整数皆为负数，则输出0
15         }
16     }
17     else{
18         int mid = (left + right) / 2;
19         int leftsum = MaxSum(a, left, mid); //求左序列最大子段和 
20         int rightsum = MaxSum(a, mid+1, right); //求右序列最大子段和 
21         
22         //求中间序列最大子段和 
23         int left_border_sum = 0;
24         int s1 = 0; //临时累加器1 
25         for(int i = mid; i >= left; i--)
26         {
27             s1 += a[i];
28             if(s1 > left_border_sum)
29             {
30                 left_border_sum = s1;
31             }
32         }
33         int right_border_sum = 0;
34         int s2 = 0; //临时累加器2 
35         for(int i = mid+1; i <= right; i++)
36         {
37             s2 += a[i];
38             if(s2 > right_border_sum)
39             {
40                 right_border_sum = s2;
41             }
42         }
43             
44         int midsum = left_border_sum + right_border_sum;
45         
46         maxsum = leftsum > rightsum ? leftsum : rightsum;
47         maxsum = midsum > maxsum ? midsum : maxsum;
48         
49         return maxsum;
50     } 
51      
52 }
53 
54 int main()
55 {
56     int K,a[200005];
57     cin>>K;
58     for(int i = 0; i < K; i++)
59     { 
60         cin>>a[i];
61     }
62     
63     cout<<MaxSum(a, 0, K-1);
64     return 0;
65 }