Start learning free

LESSON 244 OF 415 · PARTIAL SUMS #2

Max Sum of Three Subarrays in Swift: Kadane on Both Sides, O(n³)

Practice O(n3) 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
    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. It must choose three non-empty subarrays that don't overlap and return the largest possible total of their sums. A subarray is a run of neighbouring elements.

    In the example, [2, 3, -8, 7, -2, 9, -9, 7, -2, 4], the best choice is [2, 3], [7, -2, 9] and [7, -2, 4], with sums 5, 14 and 9. The total is 28. Elements -8 and -9 are left out because including them would only lower the sum.

    Approach: fix the middle subarray, let Kadane do the sides

    Three non-overlapping subarrays always come in left-to-right order: a first one, a second one in the middle, and a third one. Once the middle subarray nums[i...j] is fixed, the other two are independent of each other:

    • the first one is the best subarray that lies entirely in nums[0..<i];
    • the third one is the best subarray that lies entirely in nums[(j + 1)..<n].

    The best subarray inside a given array is the classic maximum subarray problem, solved in one pass by Kadane's algorithm. So the plan is: try every possible middle subarray, ask Kadane for the best left and right parts, add the three sums and keep the maximum.

    This is the slowest of the approaches the course covers for this problem. Later lessons precompute the best subarray on every prefix and suffix, which removes the repeated Kadane calls. Here the goal is a correct solution built from a function you already know.

    Step by step

    1. Store nums.count in n, with let, since the loops use it a lot and it never changes.
    2. Declare maxSum with var, starting at Int.min. The answer can be negative, so starting at 0 would be wrong. For [-1, -2, -3] the answer is -6.
    3. Loop over i from 1 to n - 1, the first index of the middle subarray. It starts at 1 so that the first subarray nums[0..<i] has at least one element. The last value, n - 1, leaves no room for a third subarray, but the inner loop is empty then and nothing happens.
    4. Compute sum1 as the best subarray sum of nums[0..<i], by calling maxSumSubarray. It is a let, because it doesn't change in this iteration. The slice is wrapped in Array(...), since the function takes an [Int].
    5. Start sum2 at 0 inside the loop. It is the running sum of the middle subarray for this i.
    6. Loop over j from i to n - 2, the last index of the middle subarray. The upper limit leaves at least one element for the third subarray.
    7. Add nums[j] to sum2. Each step of j extends the middle subarray by one element, so there is no need to sum it again.
    8. Compute sum3 as the best subarray sum of nums[(j + 1)..<n], again wrapped in Array(...).
    9. Update maxSum with the larger of its value and sum1 + sum2 + sum3.
    10. Return maxSum after the outer loop.
    11. Write maxSumSubarray above the main method: Kadane's algorithm. result is the best sum so far and starts at nums[0], not 0, because all the numbers may be negative. maxSum is the best sum of a subarray ending at the current element. For each val, that subarray either extends the previous one, when the previous sum is positive, or starts again at val, so maxSum = val + max(maxSum, 0). Then result takes the larger of itself and maxSum.

    The solution in Swift

    class Solution {
    func maxSumSubarray(_ nums: [Int]) -> Int {
        var result = nums[0]
        var maxSum = 0
        for val in nums {
            maxSum = val + max(maxSum, 0)
            result = max(result, maxSum)
        }
        return result
    }

    func maxSumOfThreeSubarrays(_ nums: [Int]) -> Int {
        let n = nums.count
        var maxSum = Int.min
        for i in 1..<n {
            let sum1 = maxSumSubarray(Array(nums[0..<i]))
            var sum2 = 0
            for j in i..<(n - 1) {
                sum2 += nums[j]
                let sum3 = maxSumSubarray(Array(nums[(j + 1)..<n]))
                maxSum = max(maxSum, sum1 + sum2 + sum3)
            }
        }
        return maxSum
    }
}

    Swift details worth knowing:

    • Slices are not arrays. nums[0..<i] has the type ArraySlice<Int>. It shares storage with nums and keeps the original index numbers: for [10, 20, 30, 40], the slice nums[1..<3] prints as [20, 30], its startIndex is 1, and slice[1] is 20. Array(...) turns it into a new array indexed from 0, which is what maxSumSubarray expects, and it is what makes nums[0] there the first element.
    • Half-open ranges. j + 1..<n excludes n, so nums[(j + 1)..<n] goes up to the last element. The parentheses around j + 1 make the range readable. A range whose lower bound is greater than its upper bound crashes the program, which is why the loops are written so that the lower bound never exceeds the upper bound.
    • An empty inner loop is fine. When i is n - 1, the range i..<(n - 1) is empty (both ends are n - 1) and the body doesn't run.
    • for val in nums goes over the elements directly, with no index needed in Kadane's loop.
    • Methods call each other freely. Inside the class, maxSumSubarray(...) needs no self. prefix.

    Complexity

    Time: O(n³). The two loops visit about n²/2 pairs (i, j). For each pair, building the right slice and running Kadane on it costs O(n). The left part is recomputed once per i, which adds only O(n²) in total.

    Space: O(n). Each Array(...) call copies a slice, and the copy can be as long as the input.

    The repeated Kadane calls are wasteful, because many of them work on the same suffix. Storing the best subarray sum for every prefix and every suffix once makes each lookup O(1).

    Edge cases and common mistakes

    • All negative numbers. For [-1, -2, -3] each subarray must be one element, and the answer is -6. Kadane's result starting at nums[0], and maxSum starting at Int.min, both handle this. Starting either at 0 would return a wrong value.
    • Exactly three numbers. The only choice is one element per subarray, so the answer is the total of the array. The loops allow it: i takes the values 1 and 2, and j takes only the value 1 for i = 1.
    • Empty subarrays. Starting i at 0, or letting j reach n - 1, would pass an empty slice to maxSumSubarray, where nums[0] fails because the array has no elements.
    • Forgetting Array(...). The function takes [Int], so passing the slice directly is a compile error.
    • Counting an element twice. The first slice ends before i and the third starts after j, and nums[i...j] belongs to the middle. A boundary off by one makes subarrays overlap.
    • Skipping elements between subarrays is allowed. The subarrays don't have to touch. The sides are the best subarrays inside their parts, wherever they sit.

    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