问题描述：
| 最大子数组和 | ||
|---|---|---|
| Time Limit: 1000 MS | Memory Limit: 5000 KB | |
Description
给定一个长度为N的int型数组a[0,1,2,...N-1], 请计算最大子数组和.
Input
第一行输入M表示包含M组测试数据，每组先输入N (N<=50000), 接着输入N个int型整数.
Output
输出最大子数组和.
Sample Input
2
5 -1 -5 -2 -1 -3
5 2 -1 3 -2 4
Sample Output
-1
6
问题分析：
显然该题应使用动态规划的方法求解。
可以使用动态规划来求解最大子数组和。假设dp[i]表示以第i个元素结尾的最大子数组和，那么可以得到以下状态转移方程：
dp[i] = max(dp[i-1]+a[i], a[i])
其中a[i]表示第i个元素的值。初始状态为dp[0] = a[0]。最终的答案即为dp[i]中的最大值。
时间复杂度为O(N)。
代码示例：
#include <iostream>
#include <algorithm>using namespace std;const int MAXN = 50005;int a[MAXN];
int dp[MAXN]; // dp[i]表示以第i个元素结尾的最大子数组和int main() {int T;cin >> T;while (T--) {int n;cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}dp[0] = a[0];int ans = dp[0];for (int i = 1; i < n; i++) {dp[i] = max(dp[i-1]+a[i], a[i]);//整篇代码的核心，ans = max(ans, dp[i]);}cout << ans << endl;}return 0;
}
