シーケンステーブル適用8:最大サブセグメント和のダイナミックプランニング法

シーケンステーブル適用8:最大サブセグメント和のダイナミックプランニング法
Time Limit: 5 ms Memory Limit: 500 KiB
Submit Statistic
Problem Description
n(1<=n<=10000000)個の整数(負数である可能性がある)からなるシーケンス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
1行目は整数n(1<=n<=10000000)を入力し、整数シーケンスにおけるデータ要素の個数を表す.
2行目には、順序テーブルに格納されている各データ要素の値に対応するn個の整数が順次入力されます.
Output
求めた最大サブセグメント和を出力
 
Sample Input

6
-2 11 -4 13 -5 -2

Sample Output

20

 

#include
#include
#include
using namespace std;

struct Table
{
   int *num;
   int len;
};

void build_table(Table &a, int len);
int max_sum(Table a);
void delete_memory(Table &a);

int main(void)
{
    int n, m = 0;
    Table test;

    scanf("%d", &n);
    build_table(test, n);
    m = max_sum(test);
    printf("%d
", m);
    delete_memory(test);

    return 0;
}

void build_table(Table &a, int len)
{
    a.len = len;
    a.num = new int [len + 4];
    for(int i = 1; i <= len; i++)
    {
        scanf("%d", &a.num[i]);
    }
}

int max_sum(Table a)
{
    int ans = 0, sum = 0;

    for(int i = 1; i <= a.len; i++)
    {
        sum += a.num[i];
        if(sum < 0)
        {
            sum = 0;
        }

        ans = max(ans, sum);

    }

    return ans;
}

void delete_memory(Table &a)
{
    delete []a.num;
}