游客 注册 | 登录
中文 | En

2047 - 最大子段和

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 256 MB

输入若干个整数，有正有负，要求用动态规划算法计算最大子段和，并输出这个和。注意子段为一段连续的数，同时规定全是负数的子段其和为0。

题目输入

第一行为一个整数M，代表有M组测试数据。
随后每组测试数据的第一行为N，代表该组数据有N个数。(0接下来一行给出用空格隔开的这N个整数。

题目输出

每组测试数据输出一行，即最大子段和。

输入/输出样例

输入格式

1<br/>8<br/>-2&nbsp;10&nbsp;8&nbsp;-4&nbsp;7&nbsp;5&nbsp;-29&nbsp;10<br/>

输出格式

26

C++解答

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define inf 0x7FFFFFFF
#define LL long long
#define endl '\n'
using namespace std;
long long read(){
	long long q=0,w=1;
	char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){q=q*10+(ch-'0');ch=getchar();}
	return q*w;
}
void write(LL x){
	if(x<0){putchar('-');x=(-x);}
	if(x>9)write(x/10);
	putchar('0'+x%10);
}
void writeln(LL x){write(x);puts("");}
void writecs(LL x){write(x);putchar(' ');}
const long long N = 1e7+95;
long long T,n,a[N],f[N],ans;
int main(){
	T=read();
	while(T--){
		n=read();ans=0;
		for(LL i=1;i<=n;i++)a[i]=read();
		for(LL i=1;i<=n;i++)f[i]=max(f[i-1]+a[i],a[i]);
		for(LL i=1;i<=n;i++)ans=max(ans,f[i]);
		writeln(ans);
	}
	return 0;
}
请先登陆