P5146 最大差值题解

· · 题解

题目分析

不难想到枚举 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;
}