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

Problem Description  给定n(1<=n<=100000)个整数（可能为负数）组成的序列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。 注意：本题目要求用动态规划法求解，只需要输出最大子段和的值。 Input 第一行输入整数n(1<=n<=100000)，表示整数序列中的数据元素个数； 第二行依次输入n个整数，对应顺序表中存放的每个数据元素值。 Output 输出所求的最大子段和 Sample Input 6 -2 11 -4 13 -5 -2 Sample Output 20

题解：因为小于0的记为0，所以遍历一遍顺序表就可以，如果当前的sum小于0，那么加上一定不是最优解，所以直接舍去，sum=0，比较sum和当前ans的大小，记录最大值为ans。

代码语言：javascript复制

#include <bits/stdc  .h>

using namespace std;
const int maxn = 100001;

struct node
{
    int *elem;
    int len;
};
void Creatlist(struct node &list, int n)
{
    list.elem=new int[maxn];
    if(!list.elem)
        exit(OVERFLOW);
    list.len = n;
    for(int i=0; i<n; i  )
    {
        scanf("%d",&list.elem[i]);
    }
}
int get_ans(struct node &list)
{
    int ans = 0, sum = 0;
    for(int i = 0; i < list.len; i  )
    {
        sum  = list.elem[i];
        if(sum < 0)
        {
            sum = 0;
        }
        if(sum >= ans)
        {
            ans = sum;
        }
    }
    return ans;
}

int main()
{
    int n;
    struct node list;
    scanf("%d",&n);
    Creatlist(list, n);
    int ans = get_ans(list);
    printf("%dn", ans);
    return 0;
}

input max output sample sum

0 人点赞