LESSON 232 OF 414 · PARTIAL SUMS #1

Maximum Sum Subarray in Scala: Kadane's Algorithm in O(n)

( Kadane's Algorithm )

Given an input array that may contain both positive and negative integers, find the sum of continuous subarray of numbers which has the largest sum.

Example:

Input: nums = [-2, -5, 6, -2, -3, 1, 5, -6]
Output: 7
Explanation: sum([6, -2, -3, 1, 5]) = 7

Note:

Your algorithm should run in O(n) time and use O(1) extra space.

STEP 1 OF 6

Guided

Ctrl + Enter to check

SCALA · PARTIAL SUMS #1

Maximum Sum Subarray in Scala, explained

Problem overview

The method maxSumSubarray receives an Array[Int] called nums that may hold positive and negative numbers. It returns the largest sum that any continuous run of elements can have. The run must contain at least one element, and it can be the whole array.

For nums = [-2, -5, 6, -2, -3, 1, 5, -6] the answer is 7, from the run [6, -2, -3, 1, 5]. Extending that run to the left with -5 or to the right with -6 would only lower the sum.

The statement asks for O(n) time and O(1) extra space, so one pass over the array with a few variables is the target. Checking every possible run would need two nested loops, which is too slow.

Approach: the best run that ends here

This is Kadane's algorithm. The key question to ask at each element is: what is the best sum of a run that ends exactly at this element? There are only two choices for such a run:

it extends the best run that ended at the previous element, or
it starts fresh at this element and contains only this element.

Extending is worth it only when the previous best run has a positive sum. A negative sum would drag the new total down, so the better choice is to drop it and start over. That gives the recurrence maxSum = value + math.max(maxSum, 0).

The overall answer is the largest of these "best run ending here" values over all positions, because the best run in the array has to end somewhere.

Here is the recurrence on the example. Starting from the first element, the value of maxSum after each element is:

value	maxSum	result
-2	-2	-2
-5	-5	-2
6	6	6
-2	4	6
-3	1	6
1	2	6
5	7	7
-6	1	7

At the value 6, the previous best run had a sum of -5, so the run restarts. From there it grows to 7 and the final answer is 7.

Step by step

Create result as a var holding nums(0). It stores the best sum found so far. A single element is itself a valid run, so nums(0) is a sum that really exists. Starting at 0 would be wrong: an array of only negative numbers would then answer 0, which is not the sum of any non-empty run.
Create maxSum as a var holding 0. It stores the best sum of a run ending at the current element. Before the first element there is no run, which is the same as a run whose sum is 0.
Loop over the elements with for (value <- nums). The variable is called value because val is a keyword in Scala.
Update maxSum with the recurrence. If the old maxSum is negative, math.max(maxSum, 0) turns it into 0, so the run restarts at value.
Update result with math.max(result, maxSum), so it always holds the best sum seen so far.
Return result once the loop is over.

The solution in Scala

class Solution {
    def maxSumSubarray(nums: Array[Int]): Int = {
        var result = nums(0)
        var maxSum = 0
        for (value <- nums) {
            maxSum = value + math.max(maxSum, 0)
            result = math.max(result, maxSum)
        }
        return result
    }
}

Some Scala details worth knowing:

nums(0) uses parentheses. Scala indexes an array with a method call, not square brackets. The square brackets in Array[Int] hold a type.
var versus val. Both result and maxSum are reassigned inside the loop, so they must be var. A val would give a compile error on the first reassignment.
for (value <- nums). The arrow reads "for each value taken from nums". The loop visits the elements themselves, not the indices.
math.max works on two numbers. With two Int arguments it returns an Int.
return is optional. The last expression of a block is its value, so ending the method with result on its own line does the same job. Both versions are fine here.
Int is 32 bits. Sums beyond about 2.1 billion wrap around silently. For this problem that only matters with very large inputs.

Complexity

Time: O(n). The loop touches each element once and does a constant amount of work each time.

Space: O(1). The method keeps two integers, result and maxSum, plus the loop variable, whatever the length of the array.

Edge cases and common mistakes

All numbers negative. For [-4, -1, -7] the answer is -1, the single best element. Because result starts at nums(0), this works. With result starting at 0, the answer would wrongly be 0.
One element. [5] gives 5.
Restarting too early. Comparing maxSum with 0 only decides whether to drop the past. The current value is always included, since the run must contain the element it ends at.
Forgetting to track the best. Returning maxSum instead of result gives the best run that ends at the last element. On the example that is 1, not 7.
An empty array. nums(0) throws an ArrayIndexOutOfBoundsException, so the method assumes at least one element.

Testing

[-2, -5, 6, -2, -3, 1, 5, -6] gives 7.
[-4, -1, -7] gives -1.
[5] gives 5.
[2, -1, 2] gives 3, since the -1 is worth keeping to join the two 2s.
[-3, 4, -1, 2, 1, -5, 4] gives 6.

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free