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

1741 ワード

シーケンステーブル適用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; }