你好！我是你的OI教练。这张图片总结了线性数组中非常经典且重要的一类动态规划/预处理模式——“左右模式变化”（Left-Right Pattern Variations）。你圈出的红框是其中极其关键的 Min-Max（最小-最大）模式。

为了让你在NOI（全国青少年信息学奥林匹克竞赛）体系中更好地掌握这个知识点，我将原概念转换为了标准的NOI风格试题。我们不急着写代码，先拿起草稿纸，跟着我的引导一步步来。

1. NOI风格模拟试题

题目名称： 买卖股票的最佳时机

题目描述： 给定一个长度为 $N$ 的正整数数组 $P$，其中 $P_i$ 表示某只股票在第 $i$ 天的价格。 你只有一次买入和一次卖出股票的机会（也就是说，你可以先买入，然后在未来的某一天卖出）。你不能在买入前卖出。 请你设计一个算法，计算出你能获取的最大利润。如果无法获取任何利润（例如股票价格持续下跌），则返回 $0$。

输入格式： 第一行包含一个整数 $N$ $(1 \le N \le 10^5)$，表示天数。 第二行包含 $N$ 个由空格隔开的正整数 $P_i$ $(1 \le P_i \le 10^9)$，表示每天的股票价格。

输出格式： 输出一个整数，表示能够获取的最大利润。

样例输入：

6
7 1 5 3 6 4

样例输出：

5

样例说明： 在第 2 天（价格 = 1）的时候买入，在第 5 天（价格 = 6）的时候卖出，最大利润 = 6 - 1 = 5。 注意利润不能是 7 - 1 = 6，因为买入必须在卖出之前。

2. 预备知识点总结

在解决这道题之前，你需要确信自己掌握了以下基础概念：

• 前缀与后缀极值（Prefix / Suffix Extremum）： 不仅要求前缀和，还要会求前缀最小值（dpLeft）、后缀最大值（dpRight）。这是空间换时间的核心。
• 动态规划基础（DP Base）： 理解“状态”的定义（例如：截止到第 $i$ 天的最低价格），以及简单的“状态转移方程”。
• 贪心思想（Greedy）： 要想利润最大，自然要让“买入价”尽可能低，“卖出价”尽可能高。
• 时间与空间复杂度分析： 能够区分 $O(N^2)$ 暴力算法与 $O(N)$ 优化算法的本质区别。

3. 启发式教学：草稿纸上的推理过程

同学们，现在拿起笔，在草稿纸上画出样例数据 [7, 1, 5, 3, 6, 4]。我们一步步思考。

第一步：暴力思考法（为什么会超时？）

假设我们在第 $i$ 天买入，第 $j$ 天卖出（$j > i$）。 最暴力的想法是枚举所有的 $(i, j)$ 组合，计算 $P_j - P_i$，取最大值。

• 教练提问： 这样做的时间复杂度是多少？
• 思考回答： 有两层循环，时间复杂度是 $O(N^2)$。对于 $N=10^5$ 的数据规模，$N^2 = 10^{10}$，在评测机1秒时限内一定会 Time Limit Exceeded (TLE)。

第二步：引入 Min-Max 模式（空间换时间）

我们换个角度看问题，图片红框里提示了两个数组：dpLeft (从左到右追踪最小值) 和 dpRight (从右到左追踪最大值)。

在草稿纸上画三个数组格子：

1. 原始数组 P: [ 7, 1, 5, 3, 6, 4 ]
2. 构建 dpLeft (前缀最小值):
   • 含义：dpLeft[i] 表示从第 $1$ 天到第 $i$ 天，股票的最低价格。
   • 手推一下：[ 7, 1, 1, 1, 1, 1 ] （因为一旦出现1，后面的历史最低价都是1）。
3. 构建 dpRight (后缀最大值):
   • 含义：dpRight[i] 表示从第 $i$ 天到最后一天，股票的最高价格。
   • 手推一下：从右往左看，[ 7, 6, 6, 6, 6, 4 ]。

教练引导： 现在，假设我们要把时间轴在某一天 $i$ “劈开”。我们在 $i$ 之前（包含 $i$）买入，在 $i$ 之后（包含 $i$）卖出。 那么在节点 $i$ 能产生的最大利润就是：dpRight[i] - dpLeft[i]。 我们只需要遍历一次 $i$ 从 $1$ 到 $N$，求出这个差值的最大值即可！

第三步：伪代码流程图设计

我们在写C++之前，先用逻辑流程图理清思路（注意防呆设计，已避开特殊字符）：

graph TD
    A(开始) --> B(读取天数N和数组P)
    B --> C(初始化 dpLeft 数组和 dpRight 数组)
    C --> D(从左到右循环计算 dpLeft)
    D --> E(从右到左循环计算 dpRight)
    E --> F(初始化 ans 变量为 0)
    F --> G(循环 i 从 1 到 N)
    G --> H(计算当前利润 profit 为 dpRight下标i 减去 dpLeft下标i)
    H --> I(更新 ans 为 ans 和 profit 中的较大值)
    I --> J(循环结束)
    J --> K(输出 ans)
    K --> L(结束)

第四步：复杂度分析与极致优化

• 当前时间复杂度： 预处理两个数组各遍历一次 $O(N)$，最后计算答案遍历一次 $O(N)$，总时间复杂度 $O(N)$。完美通过！
• 当前空间复杂度： 开设了两个长度为 $N$ 的数组，空间复杂度 $O(N)$。

教练的进阶挑战（时间复杂度优化建议）： 大家看草稿纸，我们真的需要把 dpLeft 和 dpRight 都完整存下来吗？ 仔细想一下，如果我们只进行一次从左到右的遍历： 当我们走到第 $i$ 天时，我们唯一想知道的是：“在我今天卖出的话，之前的最低买入价是多少？” 我们只需要一个变量 min_price 记录截止到今天的最低价，然后用今天的价格 $P_i$ 减去 min_price，就能得到“今天卖出的最大利润”。所有天的最大利润取最大值，就是全局答案。 这样，我们不仅省去了 dpRight 数组，连 dpLeft 数组也变成了一个普通变量！

• 优化后空间复杂度： $O(1)$。这就是OI竞赛中“状态压缩/滚动数组”最基础的体现。

4. 读题技巧：此类题型的关键词在哪里？

以后在考场上，看到类似的题目，重点捕捉以下关键词：

1. “先后顺序” / “时间序列”： 比如本题“必须先买入后卖出”。这说明数组具有方向性，不能随意打乱排序（sort 会破坏时间线）。
2. “最大差值” / “最大利润” / “极差”： 往往暗示你需要掌握前缀的最小值或者后缀的最大值。
3. “只有一次机会” / “最多两次” / “无数次”： 这决定了你是用简单的 Min-Max 模式（一次），还是更复杂的 状态机DP（多次）。红框里的知识点专门针对“只有一次切分点”的情况。
4. 数据范围 $N \le 10^5$ 甚至 $10^6$： 直接告诉你 $O(N^2)$ 的暴力双重循环不可取，必须通过预处理（前缀和、前缀极值）把复杂度降维到 $O(N)$ 或者 $O(N \log N)$。

现在，你可以尝试按照最后我们讨论的 $O(1)$ 空间复杂度的思路，自己去把 C++14 的代码落实下来了。加油！有卡壳的地方随时问我。