Start learning free

LESSON 234 OF 414 · PARTIAL SUMS #1

Max Sum of Three Subarrays in Scala: Brute Force in O(n^6)

Practice O(n6) 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 16
    Ctrl + Enter to check

    SCALA · PARTIAL SUMS #1

    Max Sum Of Three Subarrays in Scala, explained

    Problem overview

    The method maxSumOfThreeSubarrays receives an Array[Int] called nums with at least three numbers. It must choose three non-overlapping, non-empty, continuous subarrays so that the total of their sums is as large as possible, and return that total. The three subarrays are taken from left to right, and they can't share an element.

    In the example, nums = [2, 3, -8, 7, -2, 9, -9, 7, -2, 4]. The subarrays [2, 3], [7, -2, 9] and [7, -2, 4] have sums 5, 14 and 9, so the answer is 28. The -8 and the -9 are left out because they sit between the chosen subarrays.

    Approach: try every triple of subarrays

    This first version of the lesson is the brute force. A subarray is fixed by its first index and its last index, so three subarrays are fixed by six indices:

    i1 <= j1 < i2 <= j2 < i3 <= j3

    The code tries every such combination with six nested loops, adds up the three sums and keeps the best. Each later subarray must start after the previous one ends, which is why i2 begins at j1 + 1 and i3 at j2 + 1. That rule is what guarantees the subarrays don't overlap.

    The sums aren't recomputed from scratch each time. The loop over j1 adds nums(j1) to sum1 as the first subarray grows by one element, and the same is done for sum2 and sum3. Every time the innermost loop has extended the third subarray, the total sum1 + sum2 + sum3 is a complete candidate.

    This approach is correct but slow: the number of index combinations grows with the sixth power of n. It works for the small inputs of this lesson, and it is the starting point for the faster lessons on the same problem, which avoid trying so many combinations.

    Step by step

    1. Store the length in n with val, since it never changes and the loops use it many times.
    2. Create maxSum as a var starting at Int.MinValue. The answer can be negative, so 0 would be a wrong starting value. Int.MinValue is below every possible sum, so the first candidate replaces it.
    3. Loop i1 over all start positions of the first subarray, from 0 until n.
    4. Declare sum1 as a var equal to 0 inside that loop. Each new start gets a fresh, empty sum.
    5. Loop j1 from i1 until n, the end of the first subarray. It starts at i1 because the subarray needs at least one element.
    6. Add nums(j1) to sum1. Now sum1 is the sum of nums(i1) through nums(j1).
    7. Loop i2 from j1 + 1 until n, the start of the second subarray. It must come after the first one ends.
    8. Declare sum2 as a var equal to 0 inside that loop.
    9. Loop j2 from i2 until n, the end of the second subarray.
    10. Add nums(j2) to sum2.
    11. Loop i3 from j2 + 1 until n, the start of the third subarray.
    12. Declare sum3 as a var equal to 0 inside that loop.
    13. Loop j3 from i3 until n, the end of the third subarray.
    14. Add nums(j3) to sum3.
    15. Update maxSum with math.max(maxSum, sum1 + sum2 + sum3).
    16. Write maxSum as the last line of the method, after the outermost loop. Scala returns the last expression, so no return is needed.

    The solution in Scala

    class Solution {
    def maxSumOfThreeSubarrays(nums: Array[Int]): Int = {
        val n = nums.length
        var maxSum = Int.MinValue
        for (i1 <- 0 until n) {
            var sum1 = 0
            for (j1 <- i1 until n) {
                sum1 += nums(j1)
                for (i2 <- (j1 + 1) until n) {
                    var sum2 = 0
                    for (j2 <- i2 until n) {
                        sum2 += nums(j2)
                        for (i3 <- (j2 + 1) until n) {
                            var sum3 = 0
                            for (j3 <- i3 until n) {
                                sum3 += nums(j3)
                                maxSum = math.max(maxSum, sum1 + sum2 + sum3)
                            }
                        }
                    }
                }
            }
        }
        maxSum
    }
}

    The Scala details worth a closer look:

    • until versus to. 0 until n is a range that stops before n, while 0 to n includes n. For array indices, until is the one you want, since valid indices end at n - 1.
    • Empty ranges are fine. When j1 + 1 equals n, the range n until n is empty and the loop body simply doesn't run. That is how a subarray at the very end of the array leaves no room for the others, with no special check.
    • Where each var lives. A var declared inside a loop body is created anew on every pass. That is why sum2 and sum3 start from 0 for each new start index, while sum1 keeps growing across the j1 loop.
    • Int.MinValue is -2147483648. Adding to it would wrap around, but this code only compares it with math.max, so that never happens.
    • The parentheses in (j1 + 1) until n are optional but make the range easy to read.

    Complexity

    Time: O(n^6). Each of the six loops runs up to n times, and the loops are nested. The actual number of combinations is smaller by a constant factor, since the indices must be in increasing order, but it still grows with the sixth power. Doubling the length of the array makes the work about 64 times larger.

    Space: O(1). Only a few integers are stored.

    Edge cases and common mistakes

    • Exactly three numbers. [1, 2, 3] has only one way to split, one element per subarray, so the answer is 6.
    • All numbers negative. For [-1, -2, -3] the answer is -6, and for [-5, -1, -2, -3, -4] it is -6 too, from the single elements -1, -2 and -3. Starting maxSum at 0 would wrongly return 0.
    • Skipping elements is allowed. In [1, -5, 1, -5, 1] the answer is 3: three single-element subarrays with the two -5s left between them.
    • Starting i2 at j1. That would let the second subarray reuse the last element of the first, so the subarrays would overlap.
    • Putting var sum1 = 0 outside the i1 loop. The sum would carry over between different start positions and count elements that don't belong to the subarray.
    • Using j1 <- i1 + 1 until n. A subarray would then need at least two elements, and the single-element subarrays would be missed.

    Testing

    • [2, 3, -8, 7, -2, 9, -9, 7, -2, 4] gives 28.
    • [1, 2, 3] gives 6.
    • [-1, -2, -3] gives -6.
    • [-5, -1, -2, -3, -4] gives -6.
    • [1, -5, 1, -5, 1] gives 3.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free