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

Lokinli

发布于 2023-03-09 16:23:50

2280

发布于 2023-03-09 16:23:50

文章被收录于专栏：以终为始

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。

#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("%d\n", ans);
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-09-05，如有侵权请联系 cloudcommunity@tencent.com 删除

input