LESSON 245 OF 415 · PARTIAL SUMS #2

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

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 22

Guided

Ctrl + Enter to check

SWIFT · PARTIAL SUMS #2

Max Sum Of Three Subarrays in Swift, explained

Problem overview

The method maxSumOfThreeSubarrays receives an array nums with at least three integers. It must pick three non-empty subarrays that don't overlap and return the largest total of their sums.

For [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 and 9. The two negative numbers between them are skipped.

Approach: precompute the best subarray on every side

The three subarrays appear in left-to-right order. If the middle one is nums[i...j], then the first is the best subarray inside nums[0..<i] and the third is the best subarray inside nums[(j + 1)..<n].

A simpler solution calls the maximum-subarray routine for those two parts inside the double loop over i and j, which costs O(n³). But the two parts are always a prefix and a suffix of the array, and there are only n of each. So this lesson computes the answers once:

leftMaxSum[i] is the best subarray sum within the prefix nums[0...i];
rightMaxSum[i] is the best subarray sum within the suffix nums[i...n - 1].

After that, each lookup is a single array read, and the double loop over the middle subarray costs O(n²) in total.

The recurrence

Let maxSum be the best sum of a subarray that ends at index i. That subarray either extends the one ending at i - 1, if that sum is positive, or starts fresh at nums[i]:

maxSum = nums[i] + max(maxSum, 0)

The best subarray inside nums[0...i] either ends at i or lies inside nums[0...i - 1]:

leftMaxSum[i] = max(leftMaxSum[i - 1], maxSum)

The suffix array works the same way, scanning from the right and tracking the best subarray that starts at i.

Step by step

Store nums.count in n with let.
Create leftMaxSum with [Int](repeating: 0, count: n). It is a var, because an array declared with let can't have its elements changed.
Set leftMaxSum[0] to nums[0]. The first prefix contains one element, so that element is its only subarray.
Start maxSum at nums[0], the only subarray that ends at index 0.
Loop i from 1 to n - 1.
Update maxSum to nums[i] + Swift.max(maxSum, 0).
Fill leftMaxSum[i] with the larger of leftMaxSum[i - 1] and maxSum.
Create rightMaxSum the same way, as a var array of zeros.
Set rightMaxSum[n - 1] to nums[n - 1].
Reuse maxSum, now as the best sum of a subarray that starts at the current index, beginning with nums[n - 1].
Loop i from n - 2 down to 0. stride(from: n - 2, through: 0, by: -1) counts down and includes the end value.
Update maxSum to nums[i] + Swift.max(maxSum, 0).
Fill rightMaxSum[i] with the larger of rightMaxSum[i + 1] and maxSum.
Reset maxSum for the answer. The answer can be negative, so it must start below any possible total. The lesson uses Int(Int32.min), the smallest 32-bit integer converted to Int.
Loop over the middle subarray's first index i from 1 to n - 1, so the first subarray is not empty.
Read sum1 as leftMaxSum[i - 1]: the best first subarray, ending before index i.
Start sum2 at 0. It is a var, since it grows.
Loop j from i to n - 2, the middle subarray's last index. The limit leaves room for a non-empty third subarray.
Add nums[j] to sum2.
Read sum3 as rightMaxSum[j + 1].
Keep the larger of maxSum and sum1 + sum2 + sum3.
Return maxSum when the loops finish.

The solution in Swift

class Solution {

    func maxSumOfThreeSubarrays(_ nums: [Int]) -> Int {
        let n = nums.count

        var leftMaxSum = [Int](repeating: 0, count: n)
        leftMaxSum[0] = nums[0]
        var maxSum = nums[0]
        for i in 1..<n {
            maxSum = nums[i] + Swift.max(maxSum, 0)
            leftMaxSum[i] = Swift.max(leftMaxSum[i - 1], maxSum)
        }

        var rightMaxSum = [Int](repeating: 0, count: n)
        rightMaxSum[n - 1] = nums[n - 1]
        maxSum = nums[n - 1]
        for i in stride(from: n - 2, through: 0, by: -1) {
            maxSum = nums[i] + Swift.max(maxSum, 0)
            rightMaxSum[i] = Swift.max(rightMaxSum[i + 1], maxSum)
        }

        maxSum = Int(Int32.min)
        for i in 1..<n {
            let sum1 = leftMaxSum[i - 1]
            var sum2 = 0
            for j in i..<(n - 1) {
                sum2 += nums[j]
                let sum3 = rightMaxSum[j + 1]
                maxSum = Swift.max(maxSum, sum1 + sum2 + sum3)
            }
        }

        return maxSum
    }
}

Swift details worth knowing:

Swift.max. The module prefix selects the standard library's global max. It matters inside a class that declares its own method named max, because the method would hide the global. This class has no such method, so plain max would work here too.
[Int](repeating: 0, count: n) builds an array of n zeros, and an array declared with var can then be changed element by element.
stride for counting down. A range like (n - 2)...0 doesn't work, because a range can't go backwards (writing one crashes at run time). stride(from:through:by:) with a negative step does count down and includes the through value.
Reusing maxSum. The same variable serves three jobs: the best subarray ending at i, the best one starting at i, and finally the answer. Every use starts with an assignment, so nothing leaks from one to the next.

Complexity

Time: O(n²). Building the two arrays takes O(n) each. The double loop over i and j visits about n²/2 pairs, and each does a constant amount of work.

Space: O(n). The two arrays hold n numbers each.

The double loop is the remaining cost. The next lesson removes it by rewriting the middle sum as a difference of two prefix sums.

Edge cases and common mistakes

All negative numbers. For [-1, -2, -3] the answer is -6. Zero is a wrong starting value for the best sums, since the result would be too high.
The sentinel range. Starting the answer at Int(Int32.min) works only while the true total is above -2147483648. With three elements of -3000000000 the true answer is -9000000000, but this code returns -2147483648, because the starting value is never replaced. Int.min is a safer starting value.
Exactly three numbers. Only one choice exists, one element each, so the answer is the total. The loops handle it with i equal to 1 or 2 and a single j value.
Off-by-one on the sides. The first part for a middle subarray starting at i is leftMaxSum[i - 1], not leftMaxSum[i], which already includes nums[i]. The third part is rightMaxSum[j + 1], not rightMaxSum[j].
Forgetting that a prefix result is a maximum. leftMaxSum[i] is not "the best subarray ending at i". It is the best one anywhere in the prefix, which is why it takes the larger of the previous entry and the new maxSum.
Letting j run to n - 1. Then rightMaxSum[j + 1] reads past the end of the array and the program crashes.

Testing

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

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

Start learning free