Start learning free

LESSON 244 OF 414 · PARTIAL SUMS #2

Max Sum of Three Subarrays in Scala: O(n²) with Prefix and Suffix Arrays

Practice O(n2) Read the full explanation

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 22
    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, taken in order from left to right.

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

    Approach: precompute the best first and third subarray

    Fix the second (middle) subarray at nums[i..j]. The best first subarray is the best one anywhere in nums[0..i - 1], and the best third one is the best anywhere in nums[j + 1..n - 1]. The slower version of this lesson recomputes those two values with a fresh pass over the array for every pair (i, j), which costs O(n³) in total.

    The values depend only on where the prefix ends or where the suffix starts, so they can be computed once and stored:

    • leftMaxSum(i) is the maximum subarray sum inside nums[0..i];
    • rightMaxSum(i) is the maximum subarray sum inside nums[i..n - 1].

    Each takes one pass to fill, using the idea behind Kadane's algorithm. After that, a lookup replaces each repeated pass, and only the two loops over (i, j) remain: O(n²). In the example, leftMaxSum(2) is 5 (the subarray [2, 3]) and rightMaxSum(6) is 9 (the subarray [7, -2, 4]). With the middle subarray [7, -2, 9], which sums to 14, the total is 5 + 14 + 9 = 28.

    Step by step

    1. Store the length as val n.
    2. Create leftMaxSum with Array.fill(n)(0). It can be a val: the elements change, but the variable keeps pointing to the same array.
    3. Set leftMaxSum(0) to nums(0). The first prefix has only one subarray.
    4. Create maxSum as a var starting at nums(0). It holds the best sum of a subarray that ends at the current index.
    5. Loop i from 1 to n - 1.
    6. Update maxSum to nums(i) + math.max(maxSum, 0). The best subarray ending at i either extends the previous one, when its sum is positive, or starts at i.
    7. Fill leftMaxSum(i) as the larger of leftMaxSum(i - 1) and maxSum. The best subarray in nums[0..i] either ends at i or lies completely before it.
    8. Create rightMaxSum the same way, as an array of n zeros.
    9. Set rightMaxSum(n - 1) to nums(n - 1).
    10. Reuse maxSum, now as the best sum of a subarray that starts at the current index, beginning with nums(n - 1).
    11. Loop i downwards from n - 2 to 0, with the range n - 2 to 0 by -1. Both ends are included.
    12. Update maxSum to nums(i) + math.max(maxSum, 0), the same rule, now looking right.
    13. Fill rightMaxSum(i) as the larger of rightMaxSum(i + 1) and maxSum.
    14. Reset maxSum to Int.MinValue to hold the best answer. The answer can be negative, so 0 would be wrong.
    15. Loop i from 1 to n - 1, the possible starts of the middle subarray. Index 1 is the smallest start that leaves the first subarray non-empty.
    16. Take sum1 = leftMaxSum(i - 1): the best first subarray that ends before i.
    17. Start sum2 at 0 as a var, since it grows as the middle subarray is extended.
    18. Loop j from i to n - 2 with i until n - 1, so a non-empty third subarray remains. For i = n - 1 the loop is empty.
    19. Add nums(j) to sum2.
    20. Take sum3 = rightMaxSum(j + 1): the best third subarray that starts after j.
    21. Update maxSum with math.max(maxSum, sum1 + sum2 + sum3).
    22. End the method with maxSum. In Scala the last expression is the result, so no return is needed.

    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) + math.max(maxSum, 0)
            leftMaxSum(i) = 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) + math.max(maxSum, 0)
            rightMaxSum(i) = math.max(rightMaxSum(i + 1), maxSum)
        }

        maxSum = Int.MinValue
        for (i <- 1 until n) {
            val sum1 = leftMaxSum(i - 1)
            var sum2 = 0
            for (j <- i until n - 1) {
                sum2 += nums(j)
                val sum3 = rightMaxSum(j + 1)
                maxSum = math.max(maxSum, sum1 + sum2 + sum3)
            }
        }

        maxSum
    }
}

    The Scala details worth a closer look:

    • Array.fill(n)(0) builds an array of n zeros. The first parameter list is the size and the second is the value used to fill it.
    • val arrays are still mutable. val fixes which array the name refers to. It doesn't freeze the contents, so leftMaxSum(i) = ... is allowed.
    • n - 2 to 0 by -1 counts down, and to includes the final 0. Writing n - 2 until 0 by -1 would stop before 0 and leave rightMaxSum(0) unset.
    • Reusing a var. maxSum is assigned three different meanings in turn. That works because each phase sets it to a fresh starting value before using it.
    • The block's value. The final maxSum has no return before it. Scala evaluates it as the last expression of the method body and returns its value.

    Complexity

    Time: O(n²). Filling leftMaxSum and rightMaxSum takes one pass each. The last double loop tries each pair (i, j) with a constant amount of work per pair, which is quadratic. That beats the cubic brute force, but the next lesson reaches O(n).

    Space: O(n). The two helper arrays have n elements each.

    Edge cases and common mistakes

    • All negative numbers. [-1, -2, -3] returns -6. This is why maxSum starts at Int.MinValue for the answer and at nums(0) for the run sums.
    • Exactly three numbers. The only choice is one element each. The loops try i = 1 and j = 1: leftMaxSum(0) + nums(1) + rightMaxSum(2) is the total of all three.
    • Mixing up "best ending at i" and "best within the prefix". maxSum is the first; leftMaxSum(i) is the second. A prefix maximum must never decrease as i grows, and taking the larger of the previous value and maxSum guarantees that.
    • Using leftMaxSum(i) instead of leftMaxSum(i - 1) for the first subarray. The first subarray would then be allowed to include nums(i), which belongs to the middle one.
    • Letting j reach n - 1. rightMaxSum(j + 1) would read past the end of the array and throw an exception.
    • A downward loop that misses index 0. This happens with until instead of to in the range.

    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, from the single elements -1, -4 and -2.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free