B1589 最大部分和（连续部分和）

可以考虑双层循环，外层循环枚举起点，内层循环枚举长度，累加求和，然后打擂台找到最大的连续和。

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[110];
int main(){
	int n, ma = INT_MIN;  
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	for (int i = 0; i < n; i++){
		int s = 0;	// s 为从每个数开始的连续数和
		for (int j = i; j < n; j++){
			s += a[j];
			ma = max(s, ma);//将最大的和放进 ma 中 
		}
	}
	cout << ma; 
	return 0;
}

可以发现，这种方法的时间复杂度为 $O(n^2)$，当 $n$ 大的时候肯定会超时，那要怎么优化呢？

优化方法

维护一个dp数组，表示状态，状态dp[i] 存储以 a[i] 为结尾的连续的最大和，最后求，dp 数组的最大值就解。

对于下面的样例

7
-2 13 12 9 14 -10 2

a[i] 存储数列，dp[i] 存储状态，则有

dp[1] =a[1] = -2 第一个数组的值连续最大和是自己

那dp[2] 就不一样了，dp[2] 表示的是以a[2] 结尾的连续的最大和，那么如果前一个状态加上a[2] 的结果 比 a[i] 的值大，那么该状态肯定是 dp[1] + a[2] 了，否则，不如舍弃前面的连续最大和，只保留自己。

因为dp[1] 已经

也就是 dp[2] = max(dp[1] + a[2], a[2]);

因此，推到出状态转移方程：

d[i] = max(dp[i-1] + a[i], a[i])

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], dp[N];
int main(){
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}
	dp[1] = a[1];
	int ma = dp[1];
	for (int i = 2; i <= n; i++){
		dp[i] = max(dp[i-1] + a[i], a[i]);
	}
	for (int i = 1; i <= n; i++){
		ma = max(ma, dp[i]); 
	}
	cout << ma;
	return 0;
}