形式化题目

给定长度为 $n$ 的整数序列 $R_0, R_1, \dots, R_{n-1}$，求

其中 $n \geqslant 2$，$1 \leqslant R_t \leqslant 10^9$。

下标的大小关系 $i < j$ 表示买入必须早于卖出，这是本题唯一的顺序约束。 注意所求的最大值可以是负数：当序列严格递减时，任何一对 $i < j$ 都有 $R_j < R_i$， 此时答案是最接近 0 的那个负差。

以样例 5 3 1 3 4 3 为例，取 $i = 2$（价格 1）、$j = 4$（价格 4）得到 $4 - 1 = 3$。 其它组合都不超过 3，所以答案是 3。

暴力解法

思路

把题面要求直接翻译成两层循环。题目问的是「哪一对买入卖出时刻最划算」， 所以按卖出时刻分组：外层枚举卖出时刻 $j$，内层把它左边所有买入时刻 $i < j$ 重新扫一遍， 逐个算出 $R_j - R_i$ 并取本行最大。

选这个视角而不是「外层买入、内层卖出」，是因为题目求的是 $R_j - R_i$： 买入价在减号右边，卖出价在左边，以卖出时刻分组时，每组内部只差一个减法运算， 可以归并成「左边的最小值」；数据又是从左到右依次给出的，扫描时顺手就能维护这个最小值。

倒过来以买入时刻分组，同样能归并成「右边的最大值」，只是要倒着扫一遍。 两种写法对称，复杂度也一样；本文按从左往右的扫描讲，是因为它与输入顺序一致，代码更直白。

这个写法的正确性不需要额外论证：它枚举了全部合法下标对，一个不漏。

用样例 5 3 1 3 4 3 把每一行重扫左侧的结果列出来：

表中每一行是一次外层循环，第二列是这一行重扫左侧时的卖出价， 第四列是这一行内层循环跑出来的最大值。五行取最大得到 3，与样例输出一致。

表格还暴露了一件事：第 4 行取到最优时，左侧重扫出的最小值是 1， 也就是整个序列到此刻为止的最低价格。换句话，每一行真正被用上的只有左侧的最小值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-29 19:35
 * update_at: 2026-10-29 20:19
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 按「每个卖出时刻各挑一个买入时刻」的视角写：外层枚举卖出时刻 j，
// 内层把它左边所有 i < j 重新扫一遍，逐个算 R[j] - R[i] 取本行最大。
// 每个 j 都从头重扫左侧，共 O(n^2) 次比较，只适合 n <= 5000 的小数据。
#include <cstdio>

typedef long long ll;

const int MAXN = 5001; // 暴力只处理 n <= 5000 的小规模数据

ll n;
ll r[MAXN]; // r[i]：第 i 个时刻的价格

int main() {
    if (scanf("%lld", &n) != 1) return 0;
    if (n > MAXN - 1) { // 超出暴力适用范围，直接退出，避免越界
        fprintf(stderr, "brute.cpp 仅支持 n <= %d\n", MAXN - 1);
        return 0;
    }
    for (ll i = 0; i < n; i++) {
        scanf("%lld", &r[i]);
    }

    ll ans = -2000000000LL; // 答案可能为负，初值要比 -1e9 更小
    // 外层固定卖出时刻 j，内层把左侧的买入时刻 i 全部重扫一遍
    for (ll j = 1; j < n; j++) {
        for (ll i = 0; i < j; i++) {
            ll profit = r[j] - r[i];
            if (profit > ans) ans = profit;
        }
    }

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

复杂度

• 时间：$O(n^2)$，比较次数为 $n(n-1)/2$。
• 空间：$O(n)$，需要把整个价格序列存进数组，两层循环才能随机访问。

$n = 2 \times 10^5$ 时比较次数约 $2 \times 10^{10}$，远超 1000 ms 能完成的量级。

瓶颈

瓶颈不是「枚举」这个动作，而是左侧元素被反复重扫。

扫到 $j$ 和扫到 $j+1$ 时，内层循环要看的左侧集合只差一个元素：$j+1$ 比 $j$ 多看了 $R_j$。 可双重循环没有利用这一点，它每次都从头把左边重新走一遍，把几乎相同的计算做了 $n$ 次。

从表格里也能直接看到这层浪费：第 1 行重扫 1 个元素，第 2 行重扫 2 个，……，第 5 行重扫 5 个， 而五行真正有用的信息其实只有「左侧最小值」这一个数。

如果能把「左侧集合」压缩成一个可以增量更新的量，重复扫描就没有必要了。

正解

关键观察

对固定的卖出时刻 $j$，$R_j$ 已经是定值，要让 $R_j - R_i$ 最大，只能让 $R_i$ 尽量小。 所以 $i$ 只需要取 $[0, j-1]$ 中价格最低的那个位置，其余位置都不必再看。

于是把答案改写成一个只依赖「左侧最小值」的形式：

式子里 $R_j$ 是卖出价，$\min_{0 \leqslant i < j} R_i$ 就是 $j$ 之前出现过的最低价， 两者相减是这个卖出时刻能拿到的最好利润。

而这个最小值可以增量维护：扫到 $j$ 时的前缀最小值，等于「扫到 $j-1$ 时的前缀最小值」与 $R_{j-1}$ 中的较小者。 所以一遍扫描就够，不必回头看。

思路

用一个变量 min_price 记住「到目前为止见过的最低价」，扫描过程只有三个动作：

1. 读入当前价格 $R_j$；
2. 用 $R_j - \texttt{min\_price}$ 更新答案；
3. 用 $R_j$ 更新 min_price。

第 2 步和第 3 步的顺序不能交换。若先更新 min_price 再算利润，$R_j$ 会和自己配对， 利润至少是 0，样例 2 的 -1 就永远算不出来。 把「先算利润」写在前面的效果是：min_price 里只装着 $R_0 \dots R_{j-1}$，配对的两个时刻必满足 $i < j$。

用样例 1 走一遍，观察两个变量的变化：

表中第 $j = 2$ 行 min_price 降到 1 之后再没变过，后面三次卖出都拿它当买入价。 最终 ans = 3，出现在 $j = 4$。

正确性。 要证明的是：算法算出的 $\max_j \left(R_j - \min_{i<j} R_i\right)$ 与题面要求的 $\max_{i<j} (R_j - R_i)$ 相等。把前者记作 $A$，后者记作 $B$，分两个方向。

$A \leqslant B$（算法答案不会超过题面答案）

• 对每个 $j$，$\min_{i<j} R_i$ 一定在某个具体的下标 $i^* < j$ 上取到。
• 于是 $R_j - \min_{i<j} R_i = R_j - R_{i^*}$ 就是一个合法的买入卖出对，按定义不超过 $B$。
• 每个 $j$ 都不超过 $B$，取最大后 $A \leqslant B$。

$A \geqslant B$（题面答案不会被算法漏掉）

• 设题面的最优对是 $(i, j)$，则 $i < j$。
• $\min_{i' < j} R_{i'}$ 是 $[0, j-1]$ 上的最小值，而 $i$ 就在这个范围里，所以 $\min_{i' < j} R_{i'} \leqslant R_i$。
• 两边同取相反数得 $-\min_{i' < j} R_{i'} \geqslant -R_i$，加上 $R_j$ 得 $R_j - \min_{i' < j} R_{i'} \geqslant R_j - R_i = B$。
• 算法在 $j$ 这一轮算出的正是左端，所以 $A \geqslant B$。

两个方向合起来得 $A = B$，算法答案就是题面答案。$\square$

两个方向缺一不可：只证 $A \leqslant B$ 只能说明算法不会算出比正确答案更大的数， 无法排除它算出更小的数；只证 $A \geqslant B$ 则相反。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-29 19:35
# update_at: 2026-10-29 19:35

import sys

NEG_INF = -10**18  # 答案可能为负（价格一路下跌），初值取得足够小


def solve() -> None:
    """一遍扫描维护见过的最低价，对每个卖出时刻算出它能拿到的最大利润。"""
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    min_price = next(data)  # 第 0 个时刻只能当买入点，先把它记为最低价
    ans = NEG_INF

    for _ in range(n - 1):
        price = next(data)
        # 先算利润、再更新最低价，保证买入时刻严格早于卖出时刻
        if price - min_price > ans:
            ans = price - min_price
        if price < min_price:
            min_price = price

    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-29 19:35
 * update_at: 2026-10-29 19:35
 */
// main.cpp：ROJ 1417 最大利润（AOJ ALDS1_1_D）。
// 从左往右扫一遍，维护「扫到当前位置之前出现过的最低价格」min_price。
// 对每个卖出时刻 j，它能拿到的最大利润就是 R[j] - min_price，用它更新答案。
// 价格只被用一次，不必落地成数组：读到就更新 min_price，额外空间 O(1)。
#include <cstdio>

typedef long long ll;

const ll NEG_INF = -2000000000LL; // 答案可能为负（价格一路下跌），初值要比 -1e9 更小

ll n;
ll min_price; // min(R[0..j-1])：扫到当前时刻之前出现过的最低价格
ll ans;       // 目前见过的最好利润

void solve() {
    if (scanf("%lld", &n) != 1) return; // 单组输入：第一行 n

    ll price;
    scanf("%lld", &price);
    min_price = price; // 第 0 个时刻只能当买入点，先把它记为最低价
    ans = NEG_INF;

    for (ll j = 1; j < n; j++) {
        scanf("%lld", &price);
        // 先算利润、再更新最低价，保证买入时刻严格早于卖出时刻
        ll profit = price - min_price;
        if (profit > ans) ans = profit;
        if (price < min_price) min_price = price;
    }

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

int main() {
    solve();
    return 0;
}

复杂度

• 时间：$O(n)$。每个价格只被读一次，参与一次减法、两次比较，共 $O(1)$ 次操作。
• 空间：算法本身只用 n、min_price、ans、price 几个标量，额外空间 $O(1)$，价格读到就处理，不必存成数组。

C++ 版的 scanf 逐个读取，确实只有常数个变量；Python 版按本仓库的读入惯例用 sys.stdin.buffer.read().split() 一次性取出全部数字，输入缓冲本身占 $O(n)$ 字节。 $n = 2 \times 10^5$ 时实测峰值约 16 MB，远低于 128 MB 的限制。

对比暴力层的 $O(n^2)$，改善来自消除重复扫描：前缀最小值是一个滚动标量， 把「每个 $j$ 重扫左侧」换成了「一次比较」。

总结

本题的解法只有一步：把「枚举所有买入卖出对」换成「对每个卖出时刻，只关心它左边的最低价」。

这一步成立靠两个条件，都值得记住：

1. 目标是 $R_j - R_i$，它对 $R_i$ 单调递减，所以固定 $j$ 后最优 $i$ 唯一确定，就是左侧最小值所在的位置。
2. 左侧集合每次只增长一个元素，所以这个最小值能增量维护，不需要回头重扫。

实现上唯一容易写错的是顺序：必须先用旧的最小值算利润，再把当前价格并入最小值。 写成反序时程序不会报错，样例 1 甚至照样输出 3，但样例 2 会输出 0 而不是 -1， 一路下跌的数据全都会错。这类「顺序决定约束是否成立」的细节，用一个能暴露负答案的样例就能测出来。