代码总量回落
P5492. 代码总量回落
场次:2026年10月22日-非AI方向 · 来源:CodeFun2000 P5492
题目描述
按提交次序记录每次变更结束后的代码行数合计,记入数组 。求下标 、 满足 时 能取到的最大值。若全程没有变少,返回 。
请实现 maxLoadDrop(loads: int[]) -> int。
输入格式
一行整型数组,形如 。
约束:
输出格式
一个非负整数:最大回落幅度;不存在回落时为 。
示例
示例 1
输入:
[8, 25, 18, 22, 12, 30, 4]输出:
26说明: 从 落到 ,下降 ,比 落到 的 更大。
示例 2
输入:
[5, 6, 7, 8]输出:
0说明: 总量一路非降,没有回落。
示例 3
输入:
[100, 20]输出:
80说明: 仅一对下标,下降 。
解题思路
判定对象是「一对有序的日子」,不是两个数
这题要最大化的不是「数组里最大的数减最小的数」,而是先出现的那天减后出现的那天。 必须更早, 必须更晚,两个数的位置被绑死了。
位置约束不是形式上的。loads = [2,1,5,4] 里最大是 5、最小是 1,相减得 4;但 1 在下标 1、5 在下标 2, 反了,这一对根本不合法。六个合法数对之差分别是 、、、、、,最大值是 1。那个 5 是中途冒出来的新高,它左边没有任何比它大的值可以让它「回落」,于是它对答案毫无贡献——「最大减最小」把这种位置关系整个忽略了。
所以问题要换个问法:扫到某个 时, 选谁最好?
走到 时, 的最佳选择就是「之前见过的最大值」
固定 , 只能在 里挑。让 loads[p] - loads[q] 最大等价于让 loads[p] 最大—— 那项与 无关。所以每个位置只需要知道一件事:它左边(不含自己)出现过的最大值,记作 peak。
这就把 的对枚举压成了一次扫描:从左往右走,走到 时先拿 peak - loads[q] 更新答案,再把 loads[q] 并进 peak。先算后更新这个顺序,保证参与减法的一定是严格更早的元素。
def maxLoadDrop(loads: List[int]) -> int:
peak = loads[0] # 已经扫过的前缀最大值
best = 0 # 不下降时答案就是 0
for q in range(1, len(loads)):
# 此刻的 peak 来自 [0, q-1],满足 p < q
if peak - loads[q] > best:
best = peak - loads[q]
# 把当前值并进前缀最大值,供后面的日子使用
if loads[q] > peak:
peak = loads[q]
return best三行关键动作各自对应一个判定:
peak = loads[0]与range(1, len(loads)):第 0 天自己没有左边的日子,只能当p的候选,不能当q,所以循环从 1 开始;best = 0:题面把答案定义成非负,回落幅度全为负时(记录单调上升)答案取 0,用 0 当初值就同时覆盖了「全部相等」和「完全上升」两种情形;- 「先算差、再更新
peak」:如果反过来先更新,peak可能变成loads[q]自己,减法就成了 ,等价于允许 。对本题的答案没有影响(0 本来就在取值范围内),但它悄悄抹掉了「必须严格更早」这条约束。
为什么不需要更多状态
目标是 ,它的「最优子结构」很薄:每个位置只依赖一个数(左侧最大值),没有区间长度、没有次数限制、没有第二条边。这类结构适合一次扫描、常数个变量,peak 与 best 从 0 号位推到末尾就完事,不需要 DP 表,也不需要排序——排序反而会把「谁在前」这个唯一的约束破坏掉。
数据范围也印证了这一点: 到 , 的数对枚举约 次操作,必然超时;而一次扫描只做一遍加法和比较,稳定过。
完整代码实现
import ast
import sys
from typing import List
def maxLoadDrop(loads: List[int]) -> int:
peak = loads[0] # 已经扫过的前缀最大值
best = 0 # 不下降时答案就是 0
for q in range(1, len(loads)):
# 此刻的 peak 来自 [0, q-1],满足 p < q
if peak - loads[q] > best:
best = peak - loads[q]
# 把当前值并进前缀最大值,供后面的日子使用
if loads[q] > peak:
peak = loads[q]
return best
def solve():
line = sys.stdin.read().strip()
if not line:
return
print(maxLoadDrop(ast.literal_eval(line)))
if __name__ == "__main__":
solve()示例推演
示例 1:loads = [8, 25, 18, 22, 12, 30, 4]
peak 初值取 loads[0] = 8,best 初值 0。
loads[q] | peak(更新前) | 候选 | best | peak(更新后) | |
|---|---|---|---|---|---|
| 1 | 25 | 8 | -17 | 0 | 25 |
| 2 | 18 | 25 | 7 | 7 | 25 |
| 3 | 22 | 25 | 3 | 7 | 25 |
| 4 | 12 | 25 | 13 | 13 | 25 |
| 5 | 30 | 25 | -5 | 13 | 30 |
| 6 | 4 | 30 | 26 | 26 | 30 |
前四天都在刷新历史新高,候选值要么为负、要么只是小回落;直到第 6 天,peak 已经是 30,30 - 4 = 26 拿到最大值。输出 26,对应第 5 天的 30 回落到第 6 天的 4。
示例 2:loads = [5, 6, 7, 8]
loads[q] | peak(更新前) | 候选 | best | peak(更新后) | |
|---|---|---|---|---|---|
| 1 | 6 | 5 | -1 | 0 | 6 |
| 2 | 7 | 6 | -1 | 0 | 7 |
| 3 | 8 | 7 | -1 | 0 | 8 |
三个候选都是负数,best 保持在初值 0,返回 0。
示例 3:loads = [100, 20]
只有 :peak = 100、候选 ,best 更新为 80,返回 80。
复杂度分析
为 loads 的长度。
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 枚举所有 的数对 | 两层循环直接比, 到 时约 对,跑不完 | ||
| 前缀最大值一次扫描(最优) | 每个位置只做一次减法与一次比较,peak、best 两个变量 |
易错点总结
1. 用「全局最大减全局最小」代替扫描
把扫描整段删掉、写成 return max(loads) - min(loads),只在最小值恰好在最大值右边时才对。loads = [2,1,5,4] 会返回 ,而合法答案是 :5 在下标 2,1 在下标 1,顺序反了。这类错误不会报错、也不会越界,只是答案偏大,且越是有「后期新高」的数据偏得越多。
2. 把 peak 无条件覆盖成当前值
把循环里那个 if loads[q] > peak: 写成无条件的 peak = loads[q],历史最大值就丢了。loads = [10,5,9,1] 上: 用 10 减 5 得 5、peak 变成 5; 的 9 把 peak 抬到 9; 得 ,返回 8。正确答案是 ——那个 10 在第 1 步就被覆盖了。现象是答案偏小,而且只在「先出现峰值、中间夹一个较小值、末尾再跌」的输入上才暴露。