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

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

Problem Description

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

递归调用总次数的获得，可以参考以下求菲波那切数列的代码段中全局变量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个整数，对应顺序表中存放的每个数据元素值。

Output

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

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

Sample Input

6 -2 11 -4 13 -5 -2

Sample Output

20 11

#include <stdio.h>
#include <stdlib.h>
int a[50005], n, count=0;//定义计数变量count，初始化为0
int max(int x, int y, int z);//找到x(左区间最长子段和)，y(左区间最长子段和),z(整个区间最长子段和)的最大值
int zuida(int left, int right);//找到z(整个区间最长子段和的最大值)
int f(int left, int right);//递归函数主体
int main()
{
   
    int sum;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
   
        scanf("%d", &a[i]);
    }
    sum=f(1, n);//将初始整个的区间边间传入递归函数
    printf("%d %d\n", sum, count);
    return 0;
}
int max(int x, int y, int z)
{
   
    int rel;
    if(x>=y&&x>=z)
    {
   
        rel=x;
    }
    else if(y>=x&&y>=z)
    {
   
        rel=y;
    }
    else if(z>=x&&z>=y)
    {
   
        rel=z;
    }
    return rel;
}
int zuida(int left, int right)
{
   
    count++;//由于此函数的left， right是由递归函数中的数值传进来，因此，此函数每被调用一次，递归函数一定也被调用一次
    int thissum=0;//代表目前的最大子段和，初始化为0
    int maxsum=0;//代表整个过程中的最大字段和，初始化为0
    for(int i=left; i<=right; i++)
    {
   
        thissum+=a[i];//目前子段和为从左到右依次遍历
        if(thissum>maxsum)//目前子段和大于整体最大子段和
        {
   
            maxsum=thissum;//将整体的最大子段和进行更新
        }
        else if(thissum<0)//前一个目前子段和加上a[i]后小于0
        {
   
            thissum=0;//将目前子段和的值舍弃，在下次循环中，重新开始计算
        }
    }
    return maxsum;//将整体的最大子段和的值返回
}
int f(int left, int right)
{
   
    int i, j, k, x, y, z;
    i=left;
    j=right;
    k=(i+j)/2;
    if(i==j)
    {
   
        count++;//只要这个if起到作用，计数变量++，表示调用了一次递归函数
        return a[i];//左右区间相等，子段和最大值等于本身
    }
    else
    {
   
        x=f(i, k);//
        y=f(k+1, j);//“分”， 将原本的区间分成更小的区间， 分别求出所分成的小区间的最大子段和
        z=zuida(i, j);//求出当前整个区间的最大子段和
        return max(x, y, z);//返回x, y, z的最大值
    }
}