typo：无后效性对应 dag

就是 dp 的定义 状态设计就是计算图的节点 状态转移就是一种规定好的拓扑排序 要求无有效性就是要求计算图无环

例如 Dijkstra，s 到其余节点最短路。
已知 s 到所有节点的最短路是客观存在的
状态设计：节点 ai 代表离 s 第 i 近的边，a0 就是 s
状态转移：依据贝尔曼条件，s 到 ai 最短路是（遍历 s 到 aj 最短路 加 j 到 i 的边）的遍历最小值

这样的状态设计是有环的 s 到每个节点的最短路都依赖 s 到其他节点的最短路

dag：要求所有边是正边，这样 s 到 ai 的最短路就只需要考虑满足 j 小于 i 的 aj 了（正边条件砍掉了计算图里大概一半的边）

dag 上的数学归纳叫做拓扑排序，所有的 dp 都可以找到一个 dag 描述，dp 计算过程就是一种特殊的拓扑排序。

核心就是数学归纳法（不仅限于自然数，也可以用于 dag 等结构）和反证法

初中可能没学反证法，可以先理解这个

写到 5am 不算通宵吗

准确地说，如果内存是未初始化的，编译器可以在每次引用这部分内存时假设它是任意值（一般是对于求值来说更“方便”的值，以便进行优化），并且不需要保持前后任意次对同一块未初始化内存区域的这种假设的一致性。

但是这可能还并不能完全解释清楚程序的结果在 1 和 4 之间反复横跳的全部原因，个人建议使用 -fsanitize 编译选项，指定适当的 Sanitizer，以便更为严格地捕获异常行为。

c--的 undefined behavior 真 tm sb

不对啊，你的 max_p 在第一次塞入 max 前没有赋值？这是一个 UB(应该)，会导致你最后 input[max_p] 的时候取到不在 map 内的 key

所以 aibot，你第一句话就发现了吗？好厉害，可惜没有小费能给你 😉

建议阅读：https://www.ralfj.de/blog/2019/07/14/uninit.html

@aibot 这里可能存在的 undefined behavior 是什么？如果你能找到导致 OP 结果错误的 undefined behavior，我就会给你$10 小费

看完代码了，暂时先放一个疯四在这里 🤯

不是线性的，map 的插入查找复杂度都是 logn。
另：这个题也可以排序后双指针，总时间复杂度是一样的，留给 OP 思考