LESSON 245 OF 414 · PARTIAL SUMS #2

Max Sum of Three Subarrays in Scala: O(n) in a Single Pass

Given an array nums of integers, find three non-overlapping subarrays with maximum sum.

Return the total sum of the three subarrays

Example:

Input: [2, 3, -8, 7, -2, 9, -9, 7, -2, 4]
Output: 28
Explanation: Subarrays [2, 3], [7, -2, 9] and [7, -2, 4]
             have the maximum sum of 28

Note:

Subarrays must be non-empty
nums contains at least three numbers

STEP 1 OF 21

Guided

Ctrl + Enter to check

SCALA · PARTIAL SUMS #2

Max Sum Of Three Subarrays in Scala, explained

Problem overview

The method maxSumOfThreeSubarrays receives an array nums with at least three integers and returns the largest total of three non-empty, non-overlapping subarrays, in left-to-right order.

For nums = [2, 3, -8, 7, -2, 9, -9, 7, -2, 4] the answer is 28: the subarrays [2, 3], [7, -2, 9] and [7, -2, 4] sum to 5 + 14 + 9.

Approach: remember the best start for the middle subarray

The previous lesson stores leftMaxSum and rightMaxSum, then tries every middle subarray nums[k..i] with two nested loops, for O(n²) time. This lesson removes the inner loop.

Let sum(a..b) be the sum of nums[a..b], and let prefix(i) be the sum of nums[0..i]. If the middle subarray starts at k and ends at i, its sum is prefix(i) - prefix(k - 1). The best first subarray before it is worth leftMaxSum(k - 1). So for a fixed end i, the first two parts together are worth:

prefix(i) + (leftMaxSum(k - 1) - prefix(k - 1))

Only the bracketed part depends on k. Define maxDiff as the largest value of leftMaxSum(k - 1) - prefix(k - 1) over every start k up to i. Then for each end i the best total is prefix(i) + maxDiff + rightMaxSum(i + 1), with a single constant-time step per i, and maxDiff can be updated as i moves right.

In the example, take the middle subarray ending at index 5. Here prefix(5) is 11. The best start k is 3, with leftMaxSum(2) = 5 and prefix(2) = -3, so maxDiff is 8. The first two parts are worth 11 + 8 = 19 (which is 5 + 14), and rightMaxSum(6) = 9 adds the third: 28.

Step by step

Store the length in val n.
Create leftMaxSum as Array.fill(n)(0). The array is mutable even though the variable is a val.
Set leftMaxSum(0) to nums(0).
Start maxSum at nums(0), the best sum of a subarray ending at the current index.
Loop i from 1 to n - 1.
Update maxSum to nums(i) + scala.math.max(maxSum, 0): extend the previous subarray when its sum is positive, otherwise start fresh.
Set leftMaxSum(i) to the larger of leftMaxSum(i - 1) and maxSum.
Create rightMaxSum the same way, with n zeros.
Set rightMaxSum(n - 1) to nums(n - 1).
Reuse maxSum for the best sum of a subarray that starts at the current index, beginning at nums(n - 1).
Loop i downwards with n - 2 to 0 by -1.
Update maxSum with the same rule, then set rightMaxSum(i) to the larger of rightMaxSum(i + 1) and maxSum.
Reset maxSum to Int.MinValue to hold the answer.
Create partialSum starting at nums(0). At the beginning of each iteration it holds the sum of nums[0..i - 1].
Create maxDiff starting at Int.MinValue. It will keep the best value of leftMaxSum(k - 1) - prefix(k - 1) seen so far. The first loop iteration assigns it before anything reads it.
Loop i over the possible last elements of the middle subarray: 1 until n - 1. It needs a first subarray before it and a third one after it.
Add the option "the middle subarray starts at i". Set maxDiff to the larger of itself and leftMaxSum(i - 1) - partialSum. At this moment partialSum still equals prefix(i - 1), exactly the term needed.
Add nums(i) to partialSum. It now equals prefix(i).
Update the answer with partialSum + rightMaxSum(i + 1) + maxDiff.
End with maxSum. It is the last expression, so it is the result.

The solution in Scala

class Solution {
    def maxSumOfThreeSubarrays(nums: Array[Int]): Int = {
        val n = nums.length

        val leftMaxSum = Array.fill(n)(0)
        leftMaxSum(0) = nums(0)
        var maxSum = nums(0)
        for (i <- 1 until n) {
            maxSum = nums(i) + scala.math.max(maxSum, 0)
            leftMaxSum(i) = scala.math.max(leftMaxSum(i - 1), maxSum)
        }

        val rightMaxSum = Array.fill(n)(0)
        rightMaxSum(n - 1) = nums(n - 1)
        maxSum = nums(n - 1)
        for (i <- n - 2 to 0 by -1) {
            maxSum = nums(i) + scala.math.max(maxSum, 0)
            rightMaxSum(i) = scala.math.max(rightMaxSum(i + 1), maxSum)
        }

        maxSum = Int.MinValue
        var partialSum = nums(0)
        var maxDiff = Int.MinValue
        for (i <- 1 until n - 1) {
            maxDiff = scala.math.max(leftMaxSum(i - 1) - partialSum, maxDiff)
            partialSum += nums(i)
            maxSum = scala.math.max(partialSum + rightMaxSum(i + 1) + maxDiff, maxSum)
        }

        maxSum
    }
}

The Scala details worth a closer look:

scala.math.max is the same function as math.max. The lesson spells out the full package name; both work without an import.
Order of the two updates. The line that updates maxDiff comes before partialSum += nums(i). Swapping them would subtract the prefix that includes nums(i), which is wrong.
Int.MinValue as a start value. It works for maxDiff because the first iteration replaces it with a real value before anything adds to it. Adding to Int.MinValue or subtracting from it would wrap around silently, since Int is 32 bits.
Range 1 until n - 1. It stops at n - 2, so rightMaxSum(i + 1) never reads past the array.
Three phases, one var. maxSum serves three purposes in turn, each preceded by a fresh assignment.

Tracing the example

For the example array, leftMaxSum is [2, 5, 5, 7, 7, 14, 14, 14, 14, 14] and rightMaxSum is [14, 14, 14, 14, 9, 9, 9, 9, 4, 4]. The final loop then goes through these states:

i=1 maxDiff=0  partialSum=5  total=19
i=2 maxDiff=0  partialSum=-3 total=11
i=3 maxDiff=8  partialSum=4  total=21
i=4 maxDiff=8  partialSum=2  total=19
i=5 maxDiff=8  partialSum=11 total=28
i=6 maxDiff=8  partialSum=2  total=19
i=7 maxDiff=12 partialSum=9  total=25
i=8 maxDiff=12 partialSum=7  total=23

The largest total is 28, at i = 5. Each row is one constant-time step: no inner loop is needed to choose where the middle subarray starts.

Complexity

Time: O(n). There are three loops, each doing a constant amount of work per index: one for leftMaxSum, one for rightMaxSum and one for the final answer.

Space: O(n). The two helper arrays hold n numbers each. The remaining variables are single integers.

Edge cases and common mistakes

Exactly three numbers. The loop runs once, with i = 1, and gives the total of the three elements.
All negative numbers. [-1, -2, -3] returns -6, and [-5, -1, -4, -2, -8] returns -7. Starting the answer at 0 would break these.
Using the prefix after the update. If maxDiff uses partialSum after nums(i) was added, the middle subarray would lose its first element.
Looping to n - 1. rightMaxSum(i + 1) would be out of bounds, and no third subarray would remain anyway.
Treating maxDiff as a sum of a subarray. It is not one; it is a bookkeeping value that is combined with partialSum later and can be negative.

Testing

[2, 3, -8, 7, -2, 9, -9, 7, -2, 4] gives 28.
[-1, -2, -3] gives -6.
[-5, -1, -4, -2, -8] gives -7.

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

Start learning free