Find sub-array with the maximum sum

Problem

The problem is a follow-up to the problem MaximumSubArraySum, to provide a result that also contains the sub-array of interest, not just the sum.

This sort of problem may come up in real-life optimisation tasks.

Solution

This solution is available for purchase!

Upon purchase, you will be able to Register an account to access solutions on multiple devices.

We use Stripe for secure payment processing.


Alternatively, get unlimited solutions for $3.99 per month!

'Unlimited Scala Algorithms' gives you access to all solutions!

Test cases

assert(computeForArrayClearKadane(SampleArray).array.toList == BestSolution)
assert(computeForArrayClearKadane(SampleArray).sumSoFar == 6)

Scala Concepts

Pattern Matching

Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.

assert("Hello World".collect {
  case character if Character.isUpperCase(character) => character.toLower
} == "hw")

assert("Hello World".filter(Character.isUpperCase).map(_.toLower) == "hw")

assert((1 to 10).collect {
  case num if num % 3 == 0 => "Fizz"
  case num if num % 5 == 0 => "Buzz"
}.toList == List("Fizz", "Buzz", "Fizz", "Fizz", "Buzz"))

Pattern matching is used by methods like Collect, but can also be easily integrated into normal functions.

Pattern matches are effectively "Partial Functions", of type PartialFunction[Input, Output] which is isomorphic to Input => Option[Output]. See Option Type.

scanLeft and scanRight

Scala's `scan` functions enable you to do folds like foldLeft and foldRight, while collecting the intermediate results

This is incredibly useful when you need to collect a sequence of states, such as in MaximumSubArraySum.

Example

assert(List(1, 2, 3, 4, 5).scanLeft(0)(_ + _) == List(0, 1, 3, 6, 10, 15))

assert(List(1, 2, 3, 4, 5).scanRight(0)(_ + _) == List(15, 14, 12, 9, 5, 0))

assert(
  Iterator.from(1).scanLeft(0)(_ + _).take(5).toList == List(0, 1, 3, 6, 10)
)
View

The .view syntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.

In the example below, we can see the view in action:

var counted = 0

val resultingList = List(1, 2, 3, 4).view
  .map { num =>
    counted = counted + 1
    num + 1
  }
  .take(2)
  .toList

assert(resultingList == List(2, 3))

assert(counted == 2)

If we add a side-effect inside a map (don't do this normally!), We note that items 3 and 4 are never touched/evaluated, meaning we perform a "lazy" computation.

This is very similar to an Iterator, except views can be Indexed, and also reversed, which is a tremendously useful fact when dealing with arrays, for example when you want to zip two arrays together, such as in CheckArrayIsAPalindrome

On views, you can perform almost any typical collection operation, such as `maxBy`, `count`, `flatMap` and so forth.

And you can get views from almost any data type. Benefits other than lazy computation include potentially fusing of operations by the Java compiler, because instead of creating a new list for every stage, you evaluate new items one-by-one, meaning that if there are any optimisations to be made per one-item basis, you may get a performance boost.

Explanation

Please read the MaximumSubArraySum problem explanation for the mathematics - for this problem here, we will focus on how to attach the source array and how to get it the most efficiently.

Here, we use a 'State Machine', which lets us group together various values.

Once we have iterated through the whole array, we have a 'view' of a set of best results ending at each position. Then we pick the best one overall with `maxBy`, and from that, we extract the resulting array.

Note we use a List to store the numbers temporarily, and we do so in a reverse order (latest item goes to the front). This is because of O(1) append to the list, which is efficient.

At retrieval point, we turn that list into an array and reverse it.