3664 最大子段和之分治递归法

青旅半醒 2022-02-15 06:21 178阅读 0赞

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

Time Limit: 10 ms Memory Limit: 400 KiB

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

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

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

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

Sample Input

6
    -2 11 -4 13 -5 -2

Sample Output

20 11

#include<bits/stdc++.h>
    using namespace std;
    
    int a[50010],cnt;
    
    int fb(int l,int r){
      int sum,mid,ll=0,rr=0,suml=0,sumr=0;
      cnt++;
      if(l == r)
        return max(a[l],0);
    
      mid = (l+r)/2;
      for(int i = mid; i >= l; i--){
        suml += a[i];
        ll = max(ll,suml);
      }
      for(int i = mid+1; i <= r; i++){
        sumr += a[i];
        rr = max(rr,sumr);
      }
    
      sum = max(0,ll + rr);
      suml = fb(l,mid);
      sumr = fb(mid+1,r);
      sum = max(sum,suml);
      sum = max(sum,sumr);
      return sum;
    }
    
    int main() {
      int n;
      std::cin >> n;
      for(int i = 1; i <= n; i++)
        scanf("%d",&a[i]);
      cout << fb(1,n) << " ";
      cout << cnt << '\n';
      return 0;
    }

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