Compute maximum sum of subarray (Kadane's algorithm) in purely functional immutable Scala

Algorithm goal

Find the maximum sum of a sub-sequence of an array. This problem is known as 'MaxSliceSum' on Codility.

If we have an array like '[1, 2, -3, 4, -5]', the maximum sum of a subarray is 4, that of '[4]'.

Explanation

The mathematics

We need to break the problem down into parts: if we have a sequence \([a,b,c]\), by brute-force, we would need to look through \([a]\), \([b]\), \([c]\), \([a,b]\), \([b,c]\), and \([a,b,c]\). However, if we had computed \([a,b]\), computing \([a,b,c]\) from scratch would be redundant (as we have to do many summations more than once) and here we see a possibility of optimisation.

How do we split it into parts? If we define the result \(M_e\) to be the maximum sum of subarray ending at position \(e\), then \(M_{e+1}\) is either that, plus the value \(V_{e+1}\) at position \(e+1\), or it is the new value \(V_{e+1}\). (this is © from www.scala-algorithms.com)

This leads to a formula \(M_{e+1} = \max\{ M_e, M_e + V_{e+1}\} \), and now that we have the list of maximum subarrays ending at position \(e\), we can find the maximum value from those items.

The code

Once you understand the mathematics, the solution becomes quite straightforward.

The rest of the Explanation is available for subscribers.

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

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

Scala Concepts & Hints

Stack Safety

Stack safety is present where a function cannot crash due to overflowing the limit of number of recursive calls.

This function will work for n = 5, but will not work for n = 2000 (crash with java.lang.StackOverflowError) - however there is a way to fix it :-)

In Scala Algorithms, we try to write the algorithms in a stack-safe way, where possible, so that when you use the algorithms, they will not crash on large inputs. However, stack-safe implementations are often more complex, and in some cases, overly complex, for the task at hand.

def sum(from: Int, until: Int): Int =
  if (from == until) until else from + sum(from + 1, until)

def thisWillSucceed: Int = sum(1, 5)

def thisWillFail: Int = sum(1, 300)

Read more

View

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

Read more

scanLeft and scanRight

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

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

Read more

Algorithm in Scala

9 lines of Scala (version 2.13), showing how concise Scala can be!

This solution is available for purchase!

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

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

Test cases in Scala

assert(
  computeForArrayClearKadane(Array[Int](-2, 1, -3, 4, -1, 2, 1, -5, 4)) == 6
)
assert(computeForArrayClearKadane(Array(1, 2, -3, 4, -5)) == 4)
def computeForArrayClearKadane(array: Array[Int]): Int = ???