LESSON 243 OF 414 · PARTIAL SUMS #2

Max Sum of Three Subarrays in Scala: Brute Force with Kadane

Practice O(n³) 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 17

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 of integers with at least three numbers. It must choose three non-empty, non-overlapping subarrays, one after another, so that their combined sum is as large as possible, and return that sum. A subarray is a run of neighbouring elements.

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] sum to 5 + 14 + 9 = 28, which is the answer.

Approach: fix the middle subarray

The three subarrays appear in order: first, second, third. If you decide where the second one starts and ends, the other two are independent choices. The first can be any subarray inside the part before the second one. The third can be any subarray inside the part after it. Each of those two should simply be the best subarray in its region.

So the plan is to try every second subarray, from index i to index j, and for each one add three values: the maximum subarray sum of nums[0..i - 1], the sum of nums[i..j], and the maximum subarray sum of nums[j + 1..n - 1]. The largest total over all choices of i and j is the answer.

Finding the maximum subarray sum of a region is a known problem: Kadane's algorithm solves it in one pass. This lesson calls that helper, maxSumSubarray, on slices of the array. It is the simplest correct version. It recomputes the same regions many times, which the later lessons on this problem remove.

Step by step

Store the length in val n = nums.length, since it is used often and never changes.
Create maxSum as a var, starting at Int.MinValue. The answer can be negative, so starting at 0 could beat every real total.
Loop over i from 1 to n - 1. This is where the second subarray starts. It must be at least 1, so the first subarray nums[0..i - 1] is not empty.
Compute sum1 as maxSumSubarray(nums.slice(0, i)). The end index of slice is excluded, so this is the prefix up to i - 1. It is a val because it doesn't change during this iteration.
Start sum2 at 0 as a var, declared inside the loop for i, because each start index begins a fresh subarray.
Loop over j from i to n - 2, the possible last elements of the second subarray. Stopping at n - 2 leaves at least one element for the third. When i is n - 1 this loop doesn't run, so no total is recorded for it.
Extend the second subarray by adding nums(j) to sum2. This happens inside the inner loop, so sum2 equals the sum of nums[i..j].
Compute sum3 as the best subarray of nums.slice(j + 1, n).
Update the answer with math.max(maxSum, sum1 + sum2 + sum3).
Return maxSum after the outer loop.
Write the helper maxSumSubarray above the main method. It is Kadane's algorithm. result starts at nums(0), not 0, because every number may be negative. For each value, maxSum becomes value + math.max(maxSum, 0): the best subarray ending here either extends the previous one, when its sum is positive, or starts fresh. Then result keeps the larger of itself and maxSum.

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
    }

    def maxSumOfThreeSubarrays(nums: Array[Int]): Int = {
        val n = nums.length
        var maxSum = Int.MinValue
        for (i <- 1 until n) {
            val sum1 = maxSumSubarray(nums.slice(0, i))
            var sum2 = 0
            for (j <- i until n - 1) {
                sum2 += nums(j)
                val sum3 = maxSumSubarray(nums.slice(j + 1, n))
                maxSum = math.max(maxSum, sum1 + sum2 + sum3)
            }
        }
        return maxSum
    }
}

The Scala details worth a closer look:

slice(from, until) copies a range of the array into a new array. The end index is excluded, and a range that runs past the end is clipped. For a = [2, 3, -8, 7, -2, 9, -9, 7, -2, 4], a.slice(0, 3) is [2, 3, -8] and a.slice(8, 10) is [-2, 4].
for (value <- nums) loops over the elements themselves. The name is value rather than val, because val is a keyword.
Two variables called maxSum. The one in the helper is the best sum ending at the current element. The one in the main method is the overall answer. They live in different methods and don't interfere.
j <- i until n - 1 is the range i, i + 1, ..., n - 2. It is empty when i is n - 1.
The last expression is the result. The lesson writes return explicitly, which is fine; in idiomatic Scala the bare expression maxSum does the same.

Complexity

Let n be the length of nums.

Time: O(n³). The two loops try O(n²) pairs (i, j). For each pair, slicing and running maxSumSubarray on the part after j costs O(n). The prefix is handled once per i, which is cheaper. Together that gives O(n³).

Space: O(n). Each slice is a copy of up to n elements. The copies are short-lived, so only a few exist at a time.

This is fine for short arrays and too slow for long ones. The next lessons precompute the best prefix and suffix sums so the cubic factor disappears.

Edge cases and common mistakes

All negative numbers. For [-1, -2, -3] the answer is -6, because each subarray must hold at least one element. An Int.MinValue start for maxSum and a nums(0) start for result are what make this work.
Exactly three numbers. The only choice is one element each, so the answer is the total. The loops try i = 1, j = 1 and nothing else useful.
Starting i at 0. The first slice would be empty, and maxSumSubarray would fail on nums(0).
Letting j reach n - 1. The third slice would be empty and the helper would fail on an empty array.
Declaring sum2 outside the outer loop. It would carry the previous start index's sum into the next one.
Initialising the helper's result with 0. An all-negative region would then report 0, a sum that no non-empty subarray has.

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