Maximum subarray problem / published by https://github.com/dacr/code-examples-manager #00d54d96-94aa-4c41-a026-2eefc372ee0e/5c4bffc1ac03bf9d360a06e82b43da62cc55c23b

algo-kadane.sc

// summary : Maximum subarray problem
// keywords : scala, algorithm, scalatest, kadane, @testable
// publish : gist
// authors : David Crosson
// id : 00d54d96-94aa-4c41-a026-2eefc372ee0e
// created-on : 2019-09-19T15:04:02Z
// managed-by : https://github.com/dacr/code-examples-manager
// license : Apache License Version 2.0 (https://www.apache.org/licenses/LICENSE-2.0.txt)
// run-with : scala-cli $file

// ---------------------
//> using scala "3.4.2"
//> using dep "org.scalatest::scalatest:3.2.16"
//> using objectWrapper
// ---------------------

// https://en.wikipedia.org/wiki/Maximum_subarray_problem

import org.scalatest._, flatspec.AnyFlatSpec, matchers.should.Matchers

def maxSubarrayLegacy(nums: List[Int]): Int = {
  var bestSum = 0
  var currentSum = 0
  for {x <- nums} {
    currentSum = math.max(0, currentSum + x)
    bestSum = math.max(bestSum, currentSum)
  }
  bestSum
}

def minSubarrayLegacy(nums: List[Int]): Int = {
  var bestSum = 0
  var currentSum = 0
  for {x <- nums} {
    currentSum = math.min(0, currentSum + x)
    bestSum = math.min(bestSum, currentSum)
  }
  bestSum
}

@annotation.tailrec
def maxSubArray(nums: List[Int], bestSum: Int = 0, currentSum: Int = 0): Int = {
  if (nums.isEmpty) bestSum else {
    val newCurrentSum = math.max(0, currentSum + nums.head)
    maxSubArray(nums.tail, bestSum = math.max(bestSum, newCurrentSum), currentSum = newCurrentSum)
  }
}

@annotation.tailrec
def minSubArray(nums: List[Int], bestSum: Int = 0, currentSum: Int = 0): Int = {
  if (nums.isEmpty) bestSum else {
    val newCurrentSum = math.min(0, currentSum + nums.head)
    minSubArray(nums.tail, bestSum = math.min(bestSum, newCurrentSum), currentSum = newCurrentSum)
  }
}


class TestKadane extends AnyFlatSpec with Matchers {
  override def suiteName: String = "TestKadane"

  "Kadane algorithm" should "return the best sum" in {
    val in = List(-26, -22, -17, 16, 2, 7, 23, 20, -15, -14)
    minSubArray(in) shouldBe -65
  }
}

org.scalatest.tools.Runner.main(Array("-oDF", "-s", classOf[TestKadane].getName))