3664=顺序表应用7：最大子段和之分治递归法

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 int a[60000],c=0;
 4 int i;
 5 int max(int m,int n)
 6 {
 7     if(m>n)return m;
 8     else return n;
 9 }
10 int sum(int ii,int jj)
11 {
12     int maxsum=0;
13     c++;
14     if(ii==jj)
15     {
16         if(a[ii]>0)maxsum=a[ii];
17         else
18         {
19             maxsum=0;
20         }
21     }
22     else
23     {
24         int mid=(ii+jj)/2;
25         int lsum=sum(ii,mid);
26         int rsum=sum(mid+1,jj);
27         int ss,s1,s2;
28         s1=ss=0;
29         for(i = mid; i>=ii; --i)
30         {
31             ss+=a[i];
32             if(ss>s1)s1 = ss;
33         }
34         s2 = ss = 0;
35         for(i = mid+1; i<=jj; ++i)
36         {
37             ss+=a[i];
38             if(ss>s2)s2 = ss;
39         }
40         maxsum=s1+s2;
41         maxsum=max(maxsum,lsum);
42         maxsum=max(maxsum,rsum);
43     }
44     return maxsum;
45 }
46 int main()
47 {
48     int n;
49     scanf("%d",&n);
50     for(i=0; i<n; i++)
51     {
52         scanf("%d",&a[i]);
53     }
54     int max1=sum(0,n-1);
55     printf("%d %d\n",max1,c);
56     return 0;
57 }