75. 连续子序列的最大乘积

RT

Scala:

  // Time: O(n), Space: O(1)
  def maxProductSubseq[T](list: Iterable[T])(implicit nums: Numeric[T]): T = {
    import nums._
    if (list == null || list.isEmpty) return nums.zero

    val iter = list.iterator
    var curMax = iter.next()
    var curMin = curMax
    var max = curMax

    while (iter.hasNext) {
      val c = iter.next()
      val a = curMax * c
      val b = curMin * c
      curMax = a.max(b).max(c)
      curMin = a.min(b).min(c)
      max = max.max(curMax)
    }

    max
  }

Test:

  "Max" should {
    "max(8L, 1L, -2L, 4L, -1L) == 64L" in {
      maxProductSubseq(Seq[Long](8, 1, -2, 4, -1)) shouldBe 64L
    }
    "max(8, 1, -2, 4) == 8" in {
      maxProductSubseq(Seq(8, 1, -2, 4)) shouldBe 8
    }
    "max(8, 1, -2, 4, 3) == 12" in {
      maxProductSubseq(Array(8, 1, -2, 4, 3)) shouldBe 12
    }
  }