JZTXT

Luogu P1115 最大子段和

发布时间 2023-05-24 18:35:41作者: Gery_8002

题目描述

Link

思路

我们用一组变量记录序列 \(a[i]\), 一组变量记录当前子段和 \(b[i]\), 比较 \(b[i-1] +a[i]\) 和 \(a[i]\) 的大小, 若大于, 说明该序列数字属于子段, 否则新成一子段, 记录子段和, 与原最大子段和进行比较, 记录最大值

Code

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

int n, a[N], b[N], ans = -99999;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		b[i] = max(b[i-1]+a[i], a[i]);
		ans = max(ans, b[i]);
	}
	printf("%d", ans);
	return 0;
}