自动搬运

查看原文

来自洛谷，原作者为

	雨伞CKY 洛谷不常用｜天行健，君子以自强不息

搬运于2025-08-24 22:07:37，当前版本为作者最后更新于2021-08-28 14:59:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目分析

不难想到枚举 $i,j$ 这一暴力做法，这种做法的伪代码如下。

$$\begin{array}{ll} 1 & \textbf{for }i\gets 1\textbf{ to }n-1\\ 2 & \qquad \textbf{for }j\gets i+1\textbf{ to }n\\ 3 & \qquad\qquad\textbf{if }A[j]-A[i]\gt ans\\ 4 & \qquad\qquad\qquad ans\gets A[j]-A[i] \end{array} $$

这种做法很容易编写，但它的时间复杂度为 $O(n^{2})$。在 $2\leq n\leq 10^{6}$ 范围内，这种做法会严重超时。

我们需要找一种更快的方法才能通过本题。实际上，你不需要进行如此多次计算。你只需要在读入第 $k$ 个数时，更新此时 $A_{j}-A_{i}$ 的最大值（$A_{j}-minn_{k-1}$）和前 $k$ 个数的最小值 $minn_{k}$ 和，最后输出 $A_{j}-A_{i}$ 的最大值即可。这种做法的伪代码如下。

$$\begin{array}{ll} 1 & minn\gets A[1]\\ 2 & \textbf{for }i\gets 2\textbf{ to }n\\ 3 & \qquad\textbf{if }A[i]-minn\gt ans\\ 4 & \qquad\qquad ans\gets A[i]-minn\\ 5 & \qquad \textbf{if }A[i]\lt minn\\ 6 & \qquad\qquad minn\gets A[i] \end{array} $$

代码

#include <climits>
#include <iostream>
using namespace std;

int n;
long long int tmp,ans = LLONG_MIN,minn;

int main() {
    cin >> n >> minn;
    for (int i = 2;i <= n;i++){
        cin >> tmp;
        if (tmp - minn > ans) ans = tmp - minn;
        if (tmp < minn) minn = tmp;
    }
    cout << ans;
    return 0;
}