顺序表应用8：最大子段和之动态规划法

拼搏现实的明天。 2022-07-11 13:19 79阅读 0赞

#### Problem Description ####

给定n(1<=n<=100000)个整数（可能为负数）组成的序列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。

注意：本题目要求用动态规划法求解，只需要输出最大子段和的值。

#### Input ####

第一行输入整数n(1<=n<=100000)，表示整数序列中的数据元素个数；

第二行依次输入n个整数，对应顺序表中存放的每个数据元素值。

#### Output ####

输出所求的最大子段和

#### Example Input ####

6
    -2 11 -4 13 -5 -2

#### Example Output ####

#include<stdio.h>
    int  left, right;
    int maxinterval(int a[], int n)
    {
        int i ;
        int max=0;
        for(i=1;i<n;i++)
        {
            if(a[i-1]>0)
            {
                a[i]=a[i-1]+a[i];
            }
            else
            {
                a[i]=a[i];
                left=i;
            }
            if(a[i]>max)
            {
                right=i;
                max=a[i];
            }
        }
        return max;
    }
    int main()
    {
        int i,n;
        int a[100000] ;
        int max=0;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        max=maxinterval(a,n);
        printf("%d\n",max);
        return 0;
    }

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