最大子段和（C++，DP）

题目描述

给出一个长度为 $n$ 的序列 $a$，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 $n$。

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

7
2 -4 3 -1 2 -4 3

样例输出 #1

4

提示

样例 1 解释

选取 $[3,5]$ 子段 { 3 , − 1 , 2 } \{3, -1, 2\} {3,−1,2}，其和为 $4$。

数据规模与约定

• 对于 $40\%$ 的数据，保证 $n\le 2\times 10^3$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 2\times 10^5$，$-10^4\le a_i\le 10^4$。

解题思路：

通过样例输入进行说明

首先读入2，把2作为前缀

然后读入-4，2+(-4)=-2>-4，所以如果-4是最大子段的一部分，2一定也是最大子段的一部分

再读入3，3+(-2)=1<3，所以如果3是最大子段的一部分，2和-4一定不是最大子段的一部分

再读入-1，3+(-1)=2<3，所以如果-1是最大子段的一部分，3一定也是最大子段的一部分

再读入2，2+2=4>2，所以如果2是最大子段的一部分，3和-1一定也是最大子段的一部分

再读入-4，4+(-4)=0>-4，所以如果-4是最大子段的一部分，3、-1、2一定也是最大子段的一部分

最后读入3，0+3=3==3，所以如果3是最大子段的一部分，3、-1、2、-4一定不是最大子段的一部分

本质就是尝试给每一个数连接一个前缀，使这个数变得比自己大，如果比自己小，那么就不连接这个前缀

每次比较连接前缀后和不连接前缀二者的大小时，我们都保证了得到的是最大的前缀，同时有可能我们得到的最大前缀就是所谓的最大子段

所以本题采用的策略并不能保证最后得到的是最大子段，但我们一定曾经得到过最大子段

再加上一个变量max_num，比较每次连接的结果并存入其中

所以在读入3之后虽然我们丢弃了2和-4，但我们已经把2，2、-4这两个子段中最大者存入了max_num

最后只需要输出max_num即可

AC代码如下文章来源地址https://uudwc.com/A/19g5n

#include <iostream>
using namespace std;

int num_arr[2] = { 0 };
int max_num = 0;

int main() {
	int n, temp;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		if (i < 1) {
			max_num = temp;
			num_arr[0] = temp;
			continue;
		}
		num_arr[i % 2] = max(temp, temp + num_arr[(i + 1) % 2]);
		max_num = num_arr[i % 2] > max_num ? num_arr[i % 2] : max_num;
	}

	cout << max_num;
	return 0;
}