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

╰+攻爆jí腚メ 2022-06-07 10:38 170阅读 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 <stdio.h>
    typedef struct node
    {
        int len;
        int *elem;
    }sl;
    int k=0;
    void creat(sl &l, int n)
    {
        l.len = n;
        l.elem = new int[50020];
    }
    void scan(sl &l)
    {
        for(int i=0;i<l.len;i++)
        {
            scanf("%d",&l.elem[i]);
        }
    }
    int maxsum(sl &l, int left, int right)
    {
        k++;
        int sum = 0;
        if(left==right)
        {
            if(l.elem[left]>0)sum = l.elem[left];
            else sum = 0;
        }
        else
        {
            int m = (left+right)/2;
            int leftsum = maxsum(l,left,m);
            int rightsum = maxsum(l,m+1,right);
            int s1 = 0;
            int lefts = 0;
            for(int i = m;i>= left;i--)
            {
                lefts += l.elem[i];
                if(lefts > s1)s1 = lefts;
            }
            int s2 = 0;
            int rights = 0;
            for(int j = m+1;j<=right;j++)
            {
                rights += l.elem[j];
                if(rights > s2)s2 = rights;
            }
            sum = s1 + s2;
            if(sum < leftsum)sum = leftsum;
            if(sum < rightsum)sum = rightsum;
        }
        return sum;
    }
    int main()
    {
        int n, sum;
        sl l;
        scanf("%d",&n);
        creat(l,n);
        scan(l);
        sum = maxsum(l,0,n-1);
        printf("%d %d\n",sum, k);
        return 0;
    }

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