Start learning free

LESSON 246 OF 415 · PARTIAL SUMS #2

Max Sum of Three Subarrays in Swift: One Pass with Prefix Sums, 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 21
    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 of at least three integers and returns the largest total of three non-empty, non-overlapping subarrays. A subarray is a run of neighbouring elements.

    For [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 and 9.

    Approach: remove the loop over the middle subarray's start

    A first solution tries every middle subarray nums[k...i] with two nested loops. It combines the best subarray before the middle (the left part) with the best one after it (the right part), using Kadane's algorithm each time, and takes O(n³). A second version stores the best subarray on every prefix and every suffix, and drops to O(n²). This lesson goes one step further and needs only one loop over the middle.

    The key is to write the middle subarray's sum as a difference of prefix sums. Let P[i] be the sum of nums[0...i]. The middle subarray from k to i has the sum P[i] - P[k - 1]. With leftMaxSum and rightMaxSum as the best subarray sums on every prefix and suffix, the total for one choice is:

    leftMaxSum[k - 1] + (P[i] - P[k - 1]) + rightMaxSum[i + 1]

    Group the terms that depend on k:

    P[i] + rightMaxSum[i + 1] + (leftMaxSum[k - 1] - P[k - 1])

    For a fixed i, only the bracket depends on the start k, and k can be any value from 1 to i. So the best start is the one that maximizes leftMaxSum[k - 1] - P[k - 1]. That maximum can be kept in a variable, maxDiff, and updated as i advances: moving from i - 1 to i adds one new candidate start, k = i. No inner loop is needed.

    Step by step

    1. Store nums.count in n with let.
    2. Create leftMaxSum, a var array of n zeros, where entry i is the best subarray sum within nums[0...i].
    3. Set leftMaxSum[0] to nums[0].
    4. Start maxSum at nums[0]. It is the best sum of a subarray ending at the current index.
    5. Loop i from 1 to n - 1.
    6. Extend or restart. maxSum becomes nums[i] + max(maxSum, 0): the previous run is worth extending only when its sum is positive.
    7. Fill leftMaxSum[i] with the larger of leftMaxSum[i - 1] and maxSum. The best subarray in the prefix either ends at i or lies inside the shorter prefix.
    8. Create rightMaxSum in the same way.
    9. Set rightMaxSum[n - 1] to nums[n - 1].
    10. Reuse maxSum, now for the best sum of a subarray starting at the current index, beginning with nums[n - 1].
    11. Loop i downward from n - 2 to 0 with stride(from: n - 2, through: 0, by: -1), which includes the end value.
    12. Update maxSum to nums[i] + max(maxSum, 0).
    13. Fill rightMaxSum[i] with the larger of rightMaxSum[i + 1] and maxSum.
    14. Reset maxSum to Int.min for the final answer, which can be negative.
    15. Declare partialSum, starting at nums[0]. At the start of the iteration for index i it holds the sum of nums[0...i - 1].
    16. Declare maxDiff, starting at Int.min. It will hold the best value of leftMaxSum[k - 1] minus the sum of nums[0...k - 1] over the starts seen so far.
    17. Loop i over the middle subarray's last index, from 1 to n - 2. It needs a first subarray before it and a third after it.
    18. Add the new start. maxDiff becomes the larger of itself and leftMaxSum[i - 1] - partialSum. At this moment partialSum is the sum of nums[0...i - 1], as the formula needs for k = i.
    19. Extend the prefix. Add nums[i] to partialSum, so that it holds the sum of nums[0...i].
    20. Update the answer with the larger of itself and partialSum + rightMaxSum[i + 1] + maxDiff. This is the best first subarray plus a middle one ending at i, plus the best third one.
    21. Return maxSum after the loop.

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

        maxSum = Int.min
        var partialSum = nums[0]
        var maxDiff = Int.min
        for i in 1..<(n - 1) {
            maxDiff = max(leftMaxSum[i - 1] - partialSum, maxDiff)
            partialSum += nums[i]
            maxSum = max(partialSum + rightMaxSum[i + 1] + maxDiff, maxSum)
        }

        return maxSum
    }
}

    Swift details worth knowing:

    • The order of the two updates matters. maxDiff is updated before partialSum grows, because the candidate for start k = i needs the sum up to i - 1. Swapping the lines gives a wrong answer without any error.
    • Looping backwards. A range such as (n - 2)...0 crashes at run time, since a range can't have its lower bound above its upper bound. stride(from:through:by:) with a step of -1 counts down, and through includes the last value.
    • Int.min as a starting value. Both maxSum and maxDiff begin at Int.min and are overwritten in the first iteration before anyone uses them. The loop runs at least once because n is at least 3. Arithmetic on Int.min itself would overflow, and an overflow stops a Swift program.
    • The ranges 1..<(n - 1) and 1..<n. Both are non-empty for n >= 3. For smaller inputs 1..<(n - 1) would have its lower bound above its upper bound, which crashes.

    Complexity

    Time: O(n). There are three loops, each over at most n indices, and every iteration does a constant number of operations.

    Space: O(n). The two arrays leftMaxSum and rightMaxSum hold n numbers each. Everything else is a handful of integers.

    Edge cases and common mistakes

    • All negative numbers. For [-1, -2, -3] the answer is -6. Kadane's updates start from nums[0] and nums[n - 1], not from 0, so a negative best sum survives.
    • Exactly three numbers. Only i = 1 runs. The first and third subarrays are single elements and the answer is the total of the array.
    • Using leftMaxSum[i] instead of leftMaxSum[i - 1]. The first subarray must end before the middle one starts.
    • Updating partialSum too early. It then includes nums[i] when the start candidate is computed, and the middle subarray is counted one element short.
    • Starting maxDiff at 0. The difference can be negative, and a wrong starting value would pretend a better start exists.
    • Letting i reach n - 1. Then rightMaxSum[i + 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