最大子段和问题

最大子段和问题

——————以洛谷P1115为例

最大子段和，顾名思义就是在一段数组中选取元素和最大的子段（或最小）

这里总结了动态更新的写法：

int main()
{	
	int n, a, maxm, temp;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a);
		if (i == 0) maxm = temp = a;
		else {
			temp = max(temp + a, a);
			maxm = max(maxm, temp);
		}
	}
	printf("%d", maxm);
	return 0;
}

我们有一串 \(n\) 个元素的数据，我们在每次读入数据时就进行操作，达到节约空间的目的

最大子段和的更新策略：

显然，我们对 temp 和 maxm 进行赋初值操作，输入第一个元素时，我们将它作为 temp 和 maxm 的初值

在此之后（从第二个读入的元素开始），我们每次判断 temp + a 与 a 的大小，因为在累积 temp 这个变量时，若加上这次输入的 a 后的 temp 比 a 还要小，那么我们就可以之间从当前的 a 重新开始累积（累积完 a 还不如从 a 重新累积）

这是因为，我们的 maxm 变量存储的是过去的最大值（一直存在）

只要是 temp 的值超过了当前的 maxm ，我们就更新 maxm

注意！！！一定要对 temp 和 maxm 赋初值（赋上第一个元素的值或是一个极小值）保证不会出现初值遗留的问题