Delete and Earn问题Rust解法中scan循环逻辑解析请求

这段代码先通过fold统计数组中每个数字的出现次数，同时找出数组中的最小值min和最大值max。接着遍历从min到max的所有数字，过滤出实际存在于原数组中的数字，最终通过scan完成核心的动态规划计算。

scan循环核心变量含义 #

scan的初始状态是(0, 0, 0)，三个变量分别对应：

• a：选中当前数字时，累计的最大得分
• b：不选中当前数字时，累计的最大得分
• m：上一个处理过的数字值（用于判断当前数字和上一个是否相邻）

逐行解析scan逻辑 #

我们逐个拆解scan闭包内的代码：

1. 计算prev_max

   let prev_max = *a.max(b);
   

   这一步是拿到处理当前数字之前的全局最大得分——不管上一个数字是选还是不选，取两者的最大值即可。

2. 更新选中当前数字的得分a

   *a = if *m == n - 1 { *b } else { prev_max } + n * count;
   

   • 如果上一个数字m正好是当前数字n的前一个数（m == n-1），说明选了n就不能选m，所以只能基于不选上一个数字的最大得分b，加上当前数字的总得分n * count（每个n都能拿分，共count个）。
   • 如果上一个数字和当前数字不相邻，说明选n不影响上一个数字的选择，直接基于之前的全局最大得分prev_max，加上当前数字的总得分即可。

3. 更新不选中当前数字的得分b

   *b = prev_max;
   

   不选当前数字时，能拿到的最大得分就是处理当前数字前的全局最大得分prev_max——因为不管上一步选没选，不选当前的话最优解就是之前的最大值。

4. 更新上一个数字记录m

   *m = n;
   

   把当前数字记为“上一个处理过的数字”，方便下一轮循环判断相邻关系。

5. 返回当前阶段的最大得分

   Some(*a.max(b))
   

   每处理完一个数字，返回当前选中或不选中情况下的最大得分，最后取last()就是遍历完所有数字后的最终最大得分。

本质：动态规划的状态转移 #

这个scan逻辑其实是打家劫舍问题的变种：

• 把每个数字看作一个“房子”，房子的价值是n * count
• 规则是不能选相邻的“房子”（选了n就不能选n-1）
• a和b对应动态规划中的两个状态：选当前房子的最大价值、不选当前房子的最大价值，状态转移完全符合打家劫舍的逻辑

内容的提问来源于stack exchange，提问作者Gent Binaku