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

左手的ㄟ右手 2022-06-08 08:55 182阅读 0赞

Think:  
1知识点：分治递归法求最大子段和

[顺序表应用7：最大子段和之分治递归法——SDUT题目链接][7_SDUT]  
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\]的子段和的最大值。当所给的整数均为负数时定义子段和为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

Hint

Author

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    struct Table{
        int size;
        int *num;
    };
    
    int cnt;
    
    void build_table(Table &L, int n);/*建表*/
    int max_sum(Table L, int l, int r);/*分治递归法求解最大子段和*/
    void delete_table(Table &L);/*释放内存*/
    
    int main(){
        int n, ans;
        Table test;
        while(~scanf("%d", &n)){
            cnt = 0;
            build_table(test, n);
            ans = max_sum(test, 1, n);
            printf("%d %d\n", ans, cnt);
            delete_table(test);
        }
        return 0;
    }
    void build_table(Table &L, int n){
        L.size = n;
        L.num = new int[n+4];
        for(int i = 1; i <= n; i++){
            scanf("%d", &L.num[i]);
        }
    }
    int max_sum(Table L, int l, int r){
        cnt++;
        int sum1, sum2, sum3, sum4, mav3, mav4;
        if(l == r){
            if(L.num[l] < 0)
                return 0;
            else
                return L.num[l];
        }
        int mid = (l+r)>>1;
        sum1 = max_sum(L, l, mid);
        sum2 = max_sum(L, mid+1, r);
        sum3 = sum4 = 0, mav3 = mav4 = 0;
        for(int i = mid; i >= l; i--){
            sum3 += L.num[i];
            mav3 = max(mav3, sum3);
        }
        for(int i = mid+1; i <= r; i++){
            sum4 += L.num[i];
            mav4 = max(mav4, sum4);
        }
        int ans = 0;
        ans = max(sum1, sum2);
        ans = max(ans, mav3+mav4);
        return ans;
    }
    void delete_table(Table &L){
        delete []L.num;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 12ms
    Take Memory: 308KB
    Submit time: 2017-09-20 20:12:31
    ****************************************************/

[7_SDUT]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2223/pid/3664