Last active
May 27, 2023 06:28
-
-
Save dacr/5420134c81161d0de280bedcf3b67d3c to your computer and use it in GitHub Desktop.
Maximum subarray problem / published by https://github.com/dacr/code-examples-manager #00d54d96-94aa-4c41-a026-2eefc372ee0e/b41f43329d392d83ceabd0472ac6f6db0da04efe
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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 NON-AI License Version 2.0 (https://raw.githubusercontent.com/non-ai-licenses/non-ai-licenses/main/NON-AI-APACHE2) | |
// run-with : scala-cli $file | |
// --------------------- | |
//> using scala "3.3.0" | |
//> 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)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment