Start learning free

LESSON 235 OF 415 · PARTIAL SUMS #1

Max Sum of Three Non-Overlapping Subarrays in Swift: Brute Force

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

    SWIFT · PARTIAL SUMS #1

    Max Sum Of Three Subarrays in Swift, explained

    Problem overview

    The method maxSumOfThreeSubarrays receives an array nums of integers, with at least three elements. It must choose three non-empty, non-overlapping, continuous subarrays so that the total of their sums is as large as possible, and return that total.

    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]. Their sums are 5, 14 and 9, so the answer is 28. The -8 and the -9 sit between the chosen pieces and are left out.

    Approach: try every triple of subarrays

    This first lesson on the problem uses the most direct idea. A subarray is fixed by its first index and its last index. Three subarrays are fixed by six indices, and for them to be in order and not overlap they must satisfy:

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

    So six nested loops enumerate every valid choice. For each one, the total is sum1 + sum2 + sum3, and the answer is the largest total seen.

    The sums are not recomputed from scratch. When the end j1 moves one step right, the subarray gets one more element, so sum1 grows by nums[j1]. The same holds for sum2 and sum3. Each of the three sums is reset to 0 whenever its start index changes.

    This is slow, about O(n⁶) time, and the lessons that follow it on this problem make it faster. It is still worth writing first, because it is easy to see that it is correct: it looks at all the possibilities.

    Step by step

    1. Store the length in n. It is used in every loop bound and it never changes, so it is a let.
    2. Create maxSum as a var starting at Int.min. The best total can be negative, so 0 is not a safe start. Int.min is smaller than any possible total, so the first triple replaces it.
    3. Choose the first start i1 with a loop over every index.
    4. Create sum1 at 0 inside that loop. It is the sum of the first subarray, and each new start needs a fresh one.
    5. Choose the first end j1 from i1 to the last index. The end can equal the start, which makes a one-element subarray.
    6. Add nums[j1] to sum1. Now sum1 is the sum of nums[i1...j1].
    7. Choose the second start i2 from j1 + 1. Starting right after the first subarray is what keeps the two from overlapping.
    8. Create sum2 at 0 for each i2.
    9. Choose the second end j2 from i2 onward.
    10. Add nums[j2] to sum2.
    11. Choose the third start i3 from j2 + 1.
    12. Create sum3 at 0 for each i3.
    13. Choose the third end j3 from i3 onward.
    14. Add nums[j3] to sum3.
    15. Update maxSum with the larger of its value and sum1 + sum2 + sum3.
    16. Return maxSum after the outermost loop ends.

    The solution in Swift

    class Solution {
    func maxSumOfThreeSubarrays(_ nums: [Int]) -> Int {
        let n = nums.count
        var maxSum = Int.min
        for i1 in 0..<n {
            var sum1 = 0
            for j1 in i1..<n {
                sum1 += nums[j1]
                for i2 in (j1 + 1)..<n {
                    var sum2 = 0
                    for j2 in i2..<n {
                        sum2 += nums[j2]
                        for i3 in (j2 + 1)..<n {
                            var sum3 = 0
                            for j3 in i3..<n {
                                sum3 += nums[j3]
                                maxSum = max(maxSum, sum1 + sum2 + sum3)
                            }
                        }
                    }
                }
            }
        }
        return maxSum
    }
}

    The Swift details that matter here:

    • Half-open ranges. 0..<n runs from 0 up to n - 1. The closed range 0...n would include n, one past the last valid index.
    • Empty ranges are fine, backwards ranges are not. When j1 is the last index, (j1 + 1)..<n is n..<n, which is empty, so its loop body never runs. A range whose lower bound is larger than its upper bound crashes the program. The nested starts never go that far, because each one begins at most at n.
    • Parentheses around j1 + 1. They are not required, but they make the range easy to read.
    • var and let. The three sums and maxSum change, so they are var. The loop indices are constants that each iteration gets fresh.
    • Int.min. It is the smallest value an Int can hold. Do not add to it, because arithmetic overflow stops a Swift program with a run-time error. Here it is only compared with max, which is safe.

    Complexity

    Time: O(n⁶). There are six nested loops, each running over up to n positions, and the work inside is constant. The ordering rules shrink the real count by a constant factor, but not the exponent. Doubling the length of the array makes the program about 64 times slower, so it is only practical for small arrays.

    Space: O(1). The function uses a handful of integers.

    Edge cases and common mistakes

    • Exactly three elements. [1, 2, 3] has only one valid choice, three single-element subarrays, so the answer is 6.
    • All negative numbers. [-1, -2, -3, -4] returns -6. Each subarray must have at least one element, so the best you can do is take the three values that hurt the least. This is why maxSum starts at Int.min rather than 0.
    • Adjacent subarrays are allowed. [1, 1, 1, 1, 1] returns 5, using, for example, [1], [1] and [1, 1, 1]. Starting i2 at j1 + 2 instead of j1 + 1 would wrongly force a gap.
    • Not resetting a sum. If sum2 were declared outside the i2 loop, it would keep the total of the previous start and give wrong answers.
    • Overlap. Starting i2 at j1 would let the second subarray share an element with the first.

    Testing

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