2047 - 最大子段和
输入若干个整数，有正有负，要求用动态规划算法计算最大子段和，并输出这个和。注意子段为一段连续的数，同时规定全是负数的子段其和为0。
Input
第一行为一个整数M，代表有M组测试数据。
随后每组测试数据的第一行为N，代表该组数据有N个数。(0接下来一行给出用空格隔开的这N个整数。
Output
每组测试数据输出一行，即最大子段和。
Examples
Input
1<br/>8<br/>-2 10 8 -4 7 5 -29 10<br/>
Output
26
Hint
如果不用动态规划算法而用穷举法，则会超时。
Solution 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; }
Hint
如果不用动态规划算法而用穷举法，则会超时。