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

小灰灰 2022-07-12 04:45 112阅读 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\]的子段和的最大值。当所给的整数均为负数时定义子段和为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 <stdio.h>
    
    using namespace std;
    int count;
    
    typedef struct
    {
        int *elem;
        int len;
    }Sqlist;
    
    void create(Sqlist &l,int n)//创建顺序表
    {
        l.elem = new int[500011];
        l.len = n;
        for(int i=0; i<n; i++)
            scanf("%d",&l.elem[i]);
    }
    
    int max_sum(Sqlist &l,int left,int right)//递归先分成左右两个区间判断，求区间内最大子段
    {
        int sum = 0;
        int leftMax,rightMax;
        count++;
        if(left==right){
       //当左边和右边一样大，也就只有一个数的时候
            if(l.elem[left]>=0)
                sum = l.elem[left];
            else
                sum = 0;
        }
        else{
            int mid = (left+right)/2;
            leftMax = max_sum(l,left,mid);//分左右两段递归调用
            rightMax = max_sum(l,mid+1,right);
            int s,s1,ss;
            s = ss = 0;
            for(int i=mid; i>=left; i--){
                ss += l.elem[i];
                if(s<ss)
                    s = ss;
            }
            s1 = ss = 0;
            for(int i=mid+1; i<=right; i++){
                ss += l.elem[i];
                if(s1<ss)
                    s1 = ss;
            }
            sum = s + s1;
            if(leftMax>sum)
                sum = leftMax;
            if(rightMax>sum)
                sum = rightMax;
        }
        return sum;
    }
    
    int main()
    {
        int n,t,q;
        count = 0;
        Sqlist l;
        scanf("%d",&n);
        create(l,n);
        t = max_sum(l,0,n-1);
        printf("%d %d\n",t,count);
        return 0;
    }