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

向右看齐 2022-06-04 03:35 153阅读 0赞

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

Time Limit: 10MS  Memory Limit: 400KB

#### Problem Description ####

给定n(1<=n<=50000)个整数（可能为负数）组成的序列a\[1\],a\[2\],a\[3\],…,a\[n\],求该序列如a\[i\]+a\[i+1\]+…+a\[j\]的子段和的最大值。**当所给的整数均为[负数][Link 1]时定义子段和为0**，依此定义，所求的最优值为： Max\{0,a\[i\]+a\[i+1\]+…+a\[j\]\},1<=i<=j<=n。 例如，当（a\[1\],a\[2\],a\[3\],a\[4\],a\[5\],a\[6\]）=(-2,11,-4,13,-5,-2)时，最大子段和为20。

**注意：**本题目要求用分治递归法求解，除了需要输出最大子段和的值之外，还需要输出求得该结果所需的递归调用总次数。

递归调用总次数的获得，可以参考以下求菲波那切数列的代码段中全局变量count的用法：

\#include  
int count=0;  
int main()  
\{  
int n,m;  
int fib(int n);  
scanf("%d",&n);  
m=fib(n);  
printf("%d %d\\n",m,count);  
return 0;  
\}  
int fib(int n)  
\{  
int s;  
count++;  
if((n==1)||(n==0)) return 1;  
else s=fib(n-1)+fib(n-2);  
return s;  
\}

#### Input ####

第一行输入整数n(1<=n<=50000)，表示整数序列中的数据元素个数；

第二行依次输入n个整数，对应顺序表中存放的每个数据元素值。

#### Output ####

一行输出两个整数，之间以空格间隔输出：

第一个整数为所求的最大子段和；

第二个整数为用分治递归法求解最大子段和时，递归函数被调用的总次数。

#### Example Input ####

6
    -2 11 -4 13 -5 -2

#### Example Output ####

20 11

#include<iostream>
    #include<cstdio>
    using namespace std;
    int  count=0;
    int a[50010];
    int Max(int a[],int l,int r)
    {
         int k,sum=0;
         count++;
         if(l==r)
            return a[1]>0?a[1]:0;
         else
          {
               int mid=(l+r)/2;
               int lMax=Max(a,l,mid);
               int rMax=Max(a,mid+1,r);
               int max1=0;
               int lefts=0;
               for(k=mid;k>=l;k--)
               {
                   lefts+=a[k];
                   if(lefts>max1)
                    max1=lefts;
               }
               int max2=0;
               int rights=0;
               for(k=mid+1;k<=r;k++)
               {
                   rights+=a[k];
                   if(rights>max2)
                    max2=rights;
               }
               sum=max1+max2;
               if(sum<lMax)
                sum=lMax;
               if(sum<rMax)
                sum=rMax;
          }
          return sum;
    }
    int main()
    {
         int n,max;
         scanf("%d",&n);
         for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
         max=Max(a,1,n);
         if(max<0)
            max=0;
         printf("%d %d\n",max,count);
         return 0;
    }

[Link 1]: http://baike.baidu.com/view/71543.htm