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