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

古城微笑少年丶 2022-09-26 11:59 113阅读 0赞

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

Time Limit: 10MS Memory Limit: 400KB

[Submit][] [Statistic][]

#### 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<stdio.h> #include<stdlib.h> #include<malloc.h> #define maxsize 50020 int count;//记录递归次数 typedef struct { int *elem; int length; int stacksize; }qlist; //求最大值 int MAX(int a,int b) { if(a>=b) { return a; } else { return b; } } //初始化线性表 void Initlist(qlist &L) { //L.elem=new int[maxsize]; L.elem=(int *)malloc(maxsize*sizeof(int)); L.length=0; L.stacksize=maxsize; } //创建线性表 void Creatlist(qlist &L,int n) { for(int i=0;i<n;i++) { scanf("%d",&L.elem[i]); } L.length=n; } //分治递归求最大子段和 int maxsum(qlist &L,int left,int right) { count++; int sum=0; if(right==left)//递归边界 { if(L.elem[left]>=0) { sum=L.elem[left]; } else { sum=0; } } else { int mid; mid=(left+right)/2; int sumleft,sumright; sumleft=maxsum(L,left,mid);//分别对左半段和右半段分别递归 sumright=maxsum(L,mid+1,right); int sum1,sum2,summ; summ=sum1=0; for(int i=mid;i>=left;i--)//用for循环来求中间一段最大值 { summ+=L.elem[i]; if(summ>sum1) { sum1=summ; } } summ=sum2=0; for(int i=mid+1;i<=right;i++) { summ+=L.elem[i]; if(summ>sum2) { sum2=summ; } } sum=sum1+sum2; sum=MAX(sumleft,sum);//将左半段、右半段、中间一段比较大小求出最大值 sum=MAX(sumright,sum); } return sum; } int main() { count=0; int n; scanf("%d",&n); qlist L; Initlist(L); Creatlist(L,n); int t; t=maxsum(L,0,n-1); printf("%d %d\n",t,count); return 0; }`      ####

[Submit]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/1823/pid/3664.html
[Statistic]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/conteststatus/cid/1823/pid/3664.html
[Link 1]: http://baike.baidu.com/view/71543.htm