题解 | #最大序列和#

#include "iostream"
#include "vector"
using namespace std;

// 思路：
// 从最后一个节点出发，不断计算局部最大值并将其保存至dp
// 具体思路：对比自身 & 自身+dp[i+1] 取最大值
// 举例分析：
// 如 1 5 -3 2 4
// dp的初始状态为 0 0 0 0 4 最后一个元素为起始状态
// 开始计算倒数第二个元素 2 的dp值：对比（2，2+dp[i+1])即（2，2+4）最大值为6，dp数组更新为 0 0 0 2 4 maxDp=4
// 倒数第三个 -3 max（-3，-3+6） dp：0 0 3 2 4 maxDp=4
// 倒数第四个 5 max（5，5+3） dp:0 8 3 2 4 maxDp=8
// 最后一个 1 max(1,1+8) dp:9 8 3 2 4 maxDp=9 结果为9
// 实现过程如下
int main() {
	int num;
	while (cin >> num) {
		// define：
		vector<long long int> dp(num);					// 预分配空间
		vector<int> input(num);
		// input：
		for (int i = 0; i < num; i++) cin >> input[i];	// 输入
		// dp:
		dp[num - 1] = input[num - 1];					// 起始状态：最后一个元素的dp一定等于自身
		long long int maxDp = dp[num - 1];				// 记录全局最大值
		for (int i = input.size() - 2; i >= 0; i--) {	// 从倒数第二个开始逆向计算
			long long int temp = input[i] + dp[i + 1];	// 自身+后一个元素的字串最大值（dp）
			dp[i] = temp > input[i] ? temp : input[i];	// 记录dp：对比自身 & 自身+dp[i+1] 取最大值
			maxDp = dp[i] > maxDp ? dp[i] : maxDp;		// 记录全局最大值
		}
		// output：
		cout << maxDp << endl;
	}
	return 0;
}