如何用List.fold_left/right、List.map求列表两最大值之和？需替换filter

要实现不用filter、仅通过List.fold_left（或其他允许的函数）找出列表中两个最大值并求和，核心思路是在一次遍历中同时跟踪当前的前两大值，用元组作为fold_left的累加器，完全替代过滤操作。

先看你原代码的几个问题：

• 自定义的max函数逻辑错误：当b=0时直接返回a，会导致包含0的负数列表计算出错（比如max (-1) 0会错误返回-1）。
• 用x mod 最大值过滤最大值的逻辑不严谨：如果列表中有多个相同的最大值（比如[5,5,3]），x mod 5等于0会被过滤，导致第二大值错误取到3，而正确的两个最大值求和应该是10。
• 多次调用List.fold_left max效率低，且依赖filter不符合要求。

解决方案代码 #

(* 正确的两数取大函数 *)
let max a b = if a > b then a else b

(* 更新前两大值的函数：接收当前的(第一大, 第二大)和新元素，返回更新后的元组 *)
let update_top2 (first, second) num =
  if num > first then
    (num, first)
  else if num > second then
    (first, num)
  else
    (first, second)

let sum_two_max lst =
  match lst with
  | [] -> 0  (* 空列表返回0，可根据需求调整 *)
  | [x] -> x (* 单元素列表返回自身，因为只有一个最大值 *)
  | h1::h2::t ->
      (* 初始化累加器：前两个元素的大小关系整理成(大, 小) *)
      let init_first = max h1 h2 in
      let init_second = if h1 > h2 then h2 else h1 in
      let (final_first, final_second) = List.fold_left update_top2 (init_first, init_second) t in
      final_first + final_second

逻辑说明 #

1. update_top2函数：这是fold的核心处理函数，每次拿到当前的前两大值和新元素，判断新元素的位置：
   • 如果新元素比第一大值还大，那么它成为新的第一大，原来的第一大退居第二大；
   • 如果新元素介于第一大和第二大之间，那么它替换第二大值；
   • 否则保持原有前两大值不变。
2. 初始化累加器：对于至少两个元素的列表，先把前两个元素的大小关系整理成(第一大, 第二大)，作为fold的初始值；
3. fold遍历：一次遍历整个列表剩余元素，更新前两大值，最后求和。

这个方案全程只用了List.fold_left，没有用filter或递归，同时处理了单元素、多重复最大值等边界情况。

测试用例示例：

• sum_two_max [3;1;4;1;5;9;2;6] → 9+6=15
• sum_two_max [5;5;3] →5+5=10
• sum_two_max [0;-1;-3] →0+(-1)=-1
• sum_two_max [7] →7
• sum_two_max [] →0

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