如何用Scala函数式风格实现最长递增子数组求解？

我们可以用命令式风格实现最长递增子数组（对应LeetCode题目Longest Continuous Increasing Subsequence），代码如下：

def findLengthOfLCIS(nums: Array[Int]): Int = {
  var len = 0
  var left = 0
  for (i <- nums.indices) {
    if (i > 0 && nums(i) <= nums(i - 1)) left = i
    len = math.max(len, i - left + 1)
  }
  len
}

现在需要编写无循环、无索引的函数式解法，同时要求能返回所有递增子数组。我写出了如下解法，虽然可以正常运行，但结构过于复杂，想请教如何简化：

def findLengthOfLCIS(nums: Array[Int]): Int = {

  @annotation.tailrec
  def spanIncreasing(xs: List[Int], result: List[Int]): (List[Int], List[Int]) = xs match {
    case x :: tail if result.isEmpty || x > result.head => spanIncreasing(tail, x :: result)
    case _ => (result.reverse, xs)
  }

  @annotation.tailrec
  def dropNotIncreasing(xs: List[Int]): List[Int] = xs match {
    case x :: y :: tail if x >= y => dropNotIncreasing(y :: tail)
    case _ => xs
  }

  def step(pair: (List[Int], List[Int])): (List[Int], List[Int]) = {
    spanIncreasing(pair._1, Nil) match {
      case (increasing, tmp) => dropNotIncreasing(tmp) -> increasing
    }
  }

  def increasingSubarrays(xs: List[Int]): Iterator[List[Int]] = {
    if (xs.isEmpty) Iterator(Nil) else
      Iterator.iterate(xs -> List.empty[Int])(step).drop(1).map(_._2).takeWhile(_.nonEmpty)
  }

  increasingSubarrays(nums.toList).map(_.size).max
}

简化思路：一次遍历拆分连续递增子数组 #

核心逻辑是通过单次遍历把原数组拆分为所有连续递增的子数组，既可以直接获取所有子数组，也能快速计算最长长度，同时避免原代码中嵌套递归、迭代器操作的复杂结构。

基础简化版（易读性优先）

def findLengthOfLCIS(nums: Array[Int]): Int = {
  // 拆分出所有连续递增子数组
  val increasingSubarrays = nums.toList.foldLeft(List.empty[List[Int]]) {
    case (Nil, num) => List(List(num))
    case (prevSub :: rest, num) =>
      if (num > prevSub.last) (prevSub :+ num) :: rest
      else List(num) :: prevSub :: rest
  }.reverse

  // 若需要返回所有递增子数组，直接返回increasingSubarrays即可
  if (increasingSubarrays.isEmpty) 0 else increasingSubarrays.map(_.length).max
}

性能优化版（避免List.last遍历）

上面的代码中prevSub.last会遍历列表末尾，长列表场景下可以优化为跟踪当前子数组的最后一个元素：

def findLengthOfLCIS(nums: Array[Int]): Int = {
  val (subarrays, _) = nums.toList.foldLeft((List.empty[List[Int]], Option.empty[Int])) {
    case ((Nil, _), num) => (List(List(num)), Some(num))
    case ((subs, Some(lastNum)), num) =>
      if (num > lastNum) {
        val updatedSub = subs.head :+ num
        (updatedSub :: subs.tail, Some(num))
      } else {
        (List(num) :: subs, Some(num))
      }
    case ((subs, None), num) => (List(List(num)), Some(num))
  }

  val reversedSubs = subarrays.reverse
  if (reversedSubs.isEmpty) 0 else reversedSubs.map(_.length).max
}

尾递归风格版

如果偏好纯尾递归实现，可以用以下写法：

def findLengthOfLCIS(nums: Array[Int]): Int = {
  @annotation.tailrec
  def splitSubarrays(xs: List[Int], current: List[Int], result: List[List[Int]]): List[List[Int]] = xs match {
    case Nil => if (current.isEmpty) result else current.reverse :: result
    case x :: tail =>
      if (current.isEmpty || x > current.head) {
        splitSubarrays(tail, x :: current, result)
      } else {
        splitSubarrays(tail, List(x), current.reverse :: result)
      }
  }

  val subarrays = splitSubarrays(nums.toList, Nil, Nil).reverse
  if (subarrays.isEmpty) 0 else subarrays.map(_.size).max
}

说明 #

• 三种写法都满足无循环、无索引的函数式要求，且能直接获取所有连续递增子数组（代码中的increasingSubarrays/reversedSubs/subarrays变量即为结果）。
• 相比原代码，去掉了多层嵌套递归和迭代器操作，结构更清晰，单次遍历的时间复杂度为O(n)，性能更优。

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