最大子段和
题目描述
给出一个长度为 $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\}$,其和为 $4$。
数据规模与约定
- 对于 $40\%$ 的数据,保证 $n \leq 2 \times 10^3$。
- 对于 $100\%$ 的数据,保证 $1 \leq n \leq 2 \times 10^5$,$-10^4 \leq a_i \leq 10^4$。
题解
不要把这题想得过于复杂 做题时我们要利用样例进行分析
如果本数加上 上一个集合内的数 大于本数自身的值 则该数也加入集合
相反 如果本数加上 上一个集合内的数 小于本数据的值 就重开一个集合 本数是该集合第一个值
(注意 此处集合概念只是为了方便理解 只需要用到累加即可做到)
朴素做法
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n;
int res = -1e4 - 10; //注意这里答案一定不要初始化为0!因为本题当所有数都是负数时,最大子段和也为负数 后面res在max比较时 就存不了答案的最优解
//题目里数据最小值为-1e4 所以我们将答案初始化为小于这个值
int g[N], f[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &g[i]);
int a, b;
for (int i = 0; i < n; i ++ )
{
if (i == 0) f[i] = g[i]; //初始化该集合的第一个数据
else
{
f[i] = max(g[i], f[i - 1] + g[i]); //往后更新时是往上一个集合内加入该元素 还是 以它自身重新创一个集合 取决于该元素加上上一个集合的值与它自身谁更大
}
}
for (int i = 0; i < n; i ++ ) res = max(res, f[i]); //遍历所有集合 选择最大值
printf("%d\n", res);
return 0;
}
一维优化
观察代码发现一重循环内只会用到当前输入的值和i-1层的集合值 故优化 可以降低空间复杂度
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n;
int res = -1e4 - 10;
int g, f;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
scanf("%d", &g);
if (i == 0) f = g;
else
{
f = max(g, f + g);
}
res = max(res, f); //直接放在循环里面 一次循环更新一次
}
printf("%d\n", res);
return 0;
}