概述

小 A 要从编号 ~1~ 的城市出发，按编号从小到大依次经过共 ~n~ 个城市，第 ~i~ 个城市的纪念品价格为 ~a_i~。他必须在某个城市买入 1 个纪念品，并在编号更大的某个城市把它卖掉（不能在同一个城市买入后立刻卖出）。要求算出最多能赚多少钱，亏钱时答案可以是负数。

形式化地说：给定长为 ~n~ 的正整数序列 ~a~，求

$$\displaystyle \max_{1 \le j < i \le n} (a_i - a_j) $$

数据范围：~2 \le n \le 2 \times 10^5~，~0 < a_i \le 2 \times 10^9~；其中 ~30\%~ 的数据满足 ~n \le 1000~。

分析

核心观察

卖出城市 ~i~ 一旦确定，买入城市 ~j~ 的选择与前缀之外的数完全无关：在 ~1 \sim i-1~ 这些城市中，买价格最低的那个一定最划算。于是

$$\displaystyle \text{ans} = \max_{1 \le i \le n} \left( a_i - \min_{1 \le j < i} a_j \right) $$

这是因为对任意合法的 ~j < i~ 都有 ~a_i - a_j \le a_i - \min_{1 \le j' < i} a_{j'}~，右侧这种取法不会漏掉任何更优的方案。

要注意下标是严格小于：处理第 ~i~ 个城市时，用于买入的那段最小值只能由前 ~i-1~ 个城市构成，第 ~i~ 个城市自己不能参与，否则就变成了同一城市买入又卖出。

思路

直接枚举买入城市和卖出城市是 ~O(n^2)~ 的，当 ~n = 2 \times 10^5~ 时约有 ~2 \times 10^{10}~ 对，必然超时。

利用核心观察，可以把「前缀最小值」在扫描过程中增量维护。设 mn 表示当前城市之前出现过的最低价，按编号从小到大读入价格，对每个 ~a_i~ 依次做两件事：

1. 用 ~a_i - \text{mn}~ 更新答案，这一步对应「在第 ~i~ 个城市卖出，在之前的最低价处买入」；
2. 再把 ~a_i~ 并入 mn，让后面的城市可以把它当作买入点。

两步的顺序不能颠倒：如果先并入、再算答案，就等价于允许在同一个城市买入又卖出，样例 2 会由 ~-1~ 变成 ~0~。

此外，题目允许亏钱，答案可能为负，所以答案初值必须取一个极小值（如 ~-2^{62}~），不能写成 ~0~。

具体示例

以样例 1 的 ~a = (2, 1, 6, 8, 4)~ 为例，mn 初值为无穷大、ans 初值为负无穷，逐项模拟：

~i~	~a_i~	计算前的 mn	候选 ~a_i - \text{mn}~	更新后的 ans	更新后的 mn
~1~	~2~	无穷大	无效	负无穷	~2~
~2~	~1~	~2~	~-1~	~-1~	~1~
~3~	~6~	~1~	~5~	~5~	~1~
~4~	~8~	~1~	~7~	~7~	~1~
~5~	~4~	~1~	~3~	~7~	~1~

最终输出 ~7~，对应在第 2 个城市花 ~1~ 元买入、在第 4 个城市花 ~8~ 元卖出。

再看样例 2 的 ~a = (10, 8, 7, 5, 3, 1)~，逐项算出的候选值依次是 ~-2, -1, -2, -2, -2~，答案为 ~-1~（第 2 个城市买入、第 3 个城市卖出，亏 ~1~ 元）。这个例子同时说明两点：答案可以为负，ans 的初值不能是 ~0~；并且这一步必须用「当前城市之前」的最小值，否则第二个城市会拿自己和自己作差，算出错误的 ~0~。

算法步骤

1. 读入城市个数 ~n~。
2. 令 mn 为正无穷（取一个比任何价格都大的数，如 ~4 \times 10^{18}~），ans 为负无穷（取 ~-4 \times 10^{18}~）。

3. 依次读入每个价格 ~a_i~：

   1. 令 ans 对 ~a_i - \text{mn}~ 取较大值（在第 ~i~ 个城市卖出）；
   2. 令 mn 对 ~a_i~ 取较小值（第 ~i~ 个城市可以成为后面的买入点）。

4. 输出 ans。

整个过程边读边算，不需要保存整个序列。

复杂度分析

• 时间复杂度：~O(n)~。每个价格只做一次减法、两次比较，共 ~n~ 轮。
• 空间复杂度：~O(1)~。只需要 mn、ans 两个变量和当前读入的值，不保存整个序列。

~n \le 2 \times 10^5~ 时运算量约 ~2 \times 10^5~ 次，任何语言的普通读入都能轻松通过。

实现注意事项

• 先算答案、后更新最小值。顺序写反就等价于允许同一城市买入又卖出，样例 2 会从 ~-1~ 变成 ~0~。
• 初值要足够小。答案可能为负，ans 初值设成 ~0~ 或 ~-1~ 都是错的，应取 ~-2^{62}~ 或更小；同理，正无穷一侧也要真的比所有价格大。
• 用 64 位整数。价格本身不超过 ~2 \times 10^9~，但初值 ~-2^{62}~ 远超 32 位 int 的范围，统一用 long long 最稳妥。
• 第一个城市没有可以买入的前驱，它对应的候选值由负无穷兜住，不会影响答案。
• 输入规模只有 ~2 \times 10^5~ 个数，用普通 cin / scanf 即可；用 cin 时习惯性关掉同步（ios::sync_with_stdio(false); cin.tie(nullptr);）更快。

源代码

#include <cstdio>
#include <algorithm>

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;

    // 只能「先买后卖」，所以答案 = max_{j < i} (a_i - a_j)。
    // 固定卖出城市 i，买入城市取 i 之前价格最低的那个即可，边扫边维护前缀最小值。
    // 答案可能为负（全程降价），初值要给得足够小。
    const long long INF = (1LL << 62);
    long long mn = INF, ans = -INF;

    for (int i = 0; i < n; ++i) {
        long long x;
        scanf("%lld", &x);
        ans = std::max(ans, x - mn);   // 在 i 卖出，在之前的最低点买入
        mn = std::min(mn, x);          // 把 i 也纳入「之前」
    }

    printf("%lld\n", ans);
    return 0;
}

import sys

def solve(a):
    """O(n) 贪心：固定卖出城市，买入价取它之前的最小值。"""
    INF = 1 << 62
    mn, ans = INF, -INF          # 答案可能为负，初值取极小
    for x in a:
        if x - mn > ans:         # 先结算：在第 i 个城市卖出
            ans = x - mn
        if x < mn:               # 再更新：第 i 个城市可以成为后面的买点
            mn = x
    return ans

def brute(a):
    """O(n^2) 暴力：枚举所有 j < i。只适合小数据。"""
    return max(a[i] - a[j] for j in range(len(a)) for i in range(j + 1, len(a)))

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    a = data[1:1 + n]
    print(solve(a))

if __name__ == "__main__":
    main()