题意概括

给定一个数组 prices，其中 prices[i] 代表某只股票在第 i 天的价格。你只能进行 一次 交易，即在某一天买入，在未来的另一天卖出。请设计一个算法，计算出能获取的最大利润。如果无法获取任何利润，则返回 0。

数据范围:

• $1 \le n \le 10^5$ (天数)
• $0 \le prices[i] \le 10^4$ (每日价格)

基础知识

本题是一个经典的动态规划或贪心问题。虽然可以用 $O(N^2)$ 的暴力法（枚举所有买入和卖出的组合）解决，但这在给定的数据范围下会超时。最优的解法是 一次遍历 (One Pass)，时间复杂度为 $O(N)$。

核心思想是：当我们遍历到第 i 天时，要想获得最大利润，我们应该在第 i 天之前价格最低的那一天买入。

因此，我们只需要在遍历价格数组时维护两个变量：

1. mnp (min price): 记录到当前天为止，所遇到的历史最低股价。
2. mxp (max profit): 记录到当前天为止，所能获得的最大利润。

遍历数组中的每个价格 p：

1. 首先，用当前价格 p 更新历史最低股价 mnp：mnp = min(mnp, p)。
2. 然后，计算如果在今天卖出能够获得多大的利润（即 p - mnp），并用这个值来更新最大利润 mxp：mxp = max(mxp, p - mnp)。

遍历结束后，mxp 中存储的就是最终的答案。这种方法本质上是在每个卖出点 i，都找到了与之匹配的最优买入点 0 到 i-1。

该算法的时间复杂度为 $O(N)$，空间复杂度为 $O(1)$。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

void run() {
    int n;
    cin >> n;

    if (n == 0) {
        cout << 0 << endl;
        return;
    }

    int mnp = INT_MAX; // 记录历史最低价格
    int mxp = 0;       // 记录最大利润

    for (int i = 0; i < n; ++i) {
        int p;
        cin >> p;

        // 更新迄今为止的最低价格
        mnp = min(mnp, p);

        // 计算今天卖出能获得的利润，并更新最大利润
        mxp = max(mxp, p - mnp);
    }

    cout << mxp << endl;
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    run();

    return 0;
}

/*
样例 1:
输入:
6
7 1 5 3 6 4
输出:
5

样例 2:
输入:
5
7 6 4 3 1
输出:
0
*/