如何将该递归函数改写为更符合FP风格的地道Scala实现

给定长度满足|S| > 5的整数序列S（可使用Array、List等任意序列结构存储），需将其拆分为3个非空连续子序列，使拆分总成本最小。

成本规则 #

• 拆分成本为拆分点对应位置的元素值，该元素不会被归入任何拆分后的子序列，示例如下：

[5, 3, 8, 2, 10932, 4, 1, 87, 1]
               ^
    若在该元素（值为10932）位置拆分，对应拆分成本为10932
该问题的最优解为：
[5, 3, 8] [10932, 4] [87, 1] -> cost = 2 + 1 = 3
         ^         ^          
箭头标注位置为拆分点，对应元素值即为拆分成本，不计入任何子序列

拆分约束 #

• 总共需要设置2个拆分点
• 不可在序列的首元素、尾元素位置设置拆分点
• 两个拆分点不可相邻，否则会拆分出空的子序列

现有索引式实现 #

当前实现基于Array的索引访问编写，采用尾递归逻辑，但不符合Scala函数式编程的惯用风格：

@tailrec
def calculateCost(arr: Array[Int], currentIndex: Int = 1, acc: (Int, Int) = (Int.MaxValue, Int.MaxValue)): Int = {
  if (currentIndex >= arr.length - 1) acc._1 + acc._2
  else {
    val next = arr.applyOrElse(currentIndex + 1, (_: Int) => Int.MaxValue)
    val current = arr(currentIndex)
    val (firstSmallest, secondSmallest) = acc
    val min = next min current
    Array(firstSmallest, secondSmallest, min).max match {
      case value if value != min =>
        calculateCost(arr, currentIndex + 2, (min, firstSmallest min secondSmallest))
      case _ =>
        calculateCost(arr, currentIndex + 1, acc)
    }
  }
}

函数式风格替代实现 #

核心思路：首先提取所有合法拆分点（即原序列去掉首尾元素后的子序列），问题转化为在该子序列中找到两个索引差至少为2的元素，使两数之和最小。以下实现均不绑定具体序列类型，无手动索引操作，保留O(n)时间复杂度。

尾递归模式匹配实现 #

通过列表解构替代索引访问，将状态更新逻辑抽为独立辅助方法，逻辑清晰且保留尾递归优化特性：

import scala.annotation.tailrec

def calculateCostFp[T <: Seq[Int]](seq: T): Int = {
  // 提取候选拆分点：排除原序列首尾元素
  val candidates = seq.init.tail

  @tailrec
  def findMinSum(remaining: List[Int], bestPair: (Int, Int) = (Int.MaxValue, Int.MaxValue)): Int = remaining match {
    case Nil => bestPair._1 + bestPair._2
    case current :: Nil =>
      val updated = updateBest(bestPair, current)
      updated._1 + updated._2
    case current :: next :: rest =>
      val currentMin = math.min(current, next)
      val updated = updateBest(bestPair, currentMin)
      findMinSum(next :: rest, updated)
  }

  @inline
  private def updateBest(best: (Int, Int), value: Int): (Int, Int) = {
    val (first, second) = best
    if (value < first) (value, first)
    else if (value < second) (first, value)
    else best
  }

  findMinSum(candidates.toList)
}

流式滑动窗口实现 #

基于迭代器的滑动窗口做流式遍历，全程无额外序列拷贝，空间复杂度O(1)，写法更简洁：

def calculateCostFpSimple[T <: Seq[Int]](seq: T): Int = {
  val candidates = seq.init.tail
  require(candidates.length >= 3, "输入序列长度需大于5")

  candidates.iterator.sliding(3).foldLeft(
    (candidates.head, Int.MaxValue)
  ) { case ((prevMin, minSum), window) =>
    val newPrevMin = math.min(prevMin, window(1))
    val currentSum = window(2) + prevMin
    (newPrevMin, math.min(minSum, currentSum))
  }._2
}

两个实现均支持传入任意Seq[Int]子类，包括List、Vector、Array、LazyList等，无需针对特定序列结构做适配。

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