本篇题解为此题较简单做法及较少码量,并且码风优良,请放心阅读。
题目简述
从数轴的原点开始向正方向走。
第一次向前走 \(a_1\) 步,第二次向前走 \(a_1+a_2\),以此类推。
求走过的最大位置。
思路
首先直接模拟时间复杂度 \(O(n^2)\),看一下数据范围 \((1 \le N \le 2 \times 10^5)\) 得知此方法会超时。
那么就需要一点优化,用前缀和即可解决此题,没学过前缀和的建议看这个。通过前缀和求出前 \(i\) 项的和就很容易解决此题了:
for(int i = 1; i <= n; i ++) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
先预处理前缀和,在预处理的过程中同步求最大值,但因为此题的答案即最大值有可能在过程中产生,故需要 \(O(N)\) 遍历前缀和求最大,此时间复杂度可以接受。
经过以上分析和前缀和优化,很容易即可得出代码了:
#include<iostream>
using namespace std;
int n, a[200005];
long long pre[200005], maxn[200005]; // 前缀和数组及最大前缀和数组
int main() {
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i]; // 预处理前缀和
maxn[i] = max(maxn[i - 1], pre[i]); // 预处理前缀和最大值
}
long long temp, ans = -0x3f3f3f3f; // ans 要求最大值,所以建议赋值一个足够小的负数
for(int i = 1; i <= n; i ++) {
ans = max(ans, maxn[i] + temp); // 遍历求最大值
temp += pre[i]; // 一点点模拟
}
cout << ans << endl; // 输出,换行好习惯
return 0;
}
\[\text{The End!}
\]
标签:pre,前缀,int,题解,最大值,long,abc182,预处理
From: https://www.cnblogs.com/So-noSlack/p/17585863.html