Start learning free

LESSON 234 OF 415 · PARTIAL SUMS #1

Maximum Sum Subarray in Swift: Prefix Sums in O(n) Time

Practice O(n) Read the full explanation

( Prefix Sums Approach )


Given an input array that may contain both positive and negative integers, find the sum of continuous subarray of numbers which has the largest sum.

Example:

Input: nums = [-2, -5, 6, -2, -3, 1, 5, -6]
Output: 7
Explanation: sum([6, -2, -3, 1, 5]) = 7

Note:

Your algorithm should run in O(n) time and use at most O(n) extra space.


STEP 1 OF 7
    Ctrl + Enter to check

    SWIFT · PARTIAL SUMS #1

    Maximum Sum Subarray in Swift, explained

    Problem overview

    The method maxSumSubarray receives an array of integers, positive or negative, and returns the largest sum of any continuous, non-empty run of elements.

    For nums = [-2, -5, 6, -2, -3, 1, 5, -6] the answer is 7, from the run [6, -2, -3, 1, 5].

    The statement allows O(n) time and up to O(n) extra space. This lesson solves it with prefix sums, and the code ends up needing only a few variables.

    Approach: a subarray sum is a difference of two prefix sums

    The prefix sum at a position is the sum of all elements from the start of the array up to that position. Take two prefix sums, one taken later than the other. Their difference is exactly the sum of the elements between them.

    That turns the problem around. A run that ends at the current position has the sum partialSum - (an earlier prefix sum). To make that as large as possible, subtract the smallest earlier prefix sum. So the best run ending here is:

    partialSum - minSum

    where minSum is the smallest prefix sum seen before the current element. The empty prefix, with sum 0, counts as an earlier prefix, which is why minSum starts at 0. It lets a run start at index 0.

    Trying every start and end is O(n²). With prefix sums, each element needs one subtraction and one comparison, so a single pass is enough.

    On the example, the table shows the running prefix sum, the best run ending at that element, the smallest earlier prefix sum after the update, and the overall best so far:

    valpartialSumpartialSum - minSumminSumresult
    -2-2-2-2-2
    -5-7-5-7-2
    6-16-76
    -2-34-76
    -3-61-76
    1-52-76
    507-77
    -6-61-77

    The smallest prefix sum, -7, appears right before the 6. Taking the prefix sum 0 at the element 5 and subtracting -7 gives 7: the run that starts just after the minimum.

    Step by step

    1. Create partialSum and minSum, both at 0. The first is the sum of everything read so far. The second is the smallest prefix sum seen so far, and the empty prefix has sum 0.
    2. Create result from nums[0]. The answer can be negative, so 0 is not a safe start. The first element is a real run, which makes it a valid starting value.
    3. Loop over the elements, naming each one val.
    4. Add val to partialSum so it covers the current element.
    5. Update result with the larger of its value and partialSum - minSum.
    6. Update minSum with the smaller of its value and the current partialSum. This comes after the result update, because a run must contain at least one element. If minSum were updated first, the current prefix could be subtracted from itself, which gives an empty run with sum 0.
    7. Return result after the loop.

    The solution in Swift

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

    A few Swift details:

    • Two variables in one declaration. var partialSum = 0, minSum = 0 declares both with var, and each one is inferred to be an Int.
    • Compound assignment. partialSum += val works for Int as in most languages. Swift has no ++ or -- operators, so += 1 is how you add one.
    • Global max and min. Both are free functions taking two values, so no object or import is needed.
    • Overflow stops the program. Int is 64 bits. If a sum goes beyond its range, Swift traps at run time instead of wrapping around. Ordinary test values never get near it.
    • Empty input. nums[0] crashes on an empty array, so the code relies on the lesson's guarantee of at least one element.

    Complexity

    Time: O(n). One pass, with a constant number of operations per element.

    Space: O(1). The prefix sums are never stored in an array. Only the latest one and the smallest one are needed, and that stays within the statement's O(n) allowance with room to spare.

    Kadane's version of the problem, which tracks the best run ending at each element directly, has the same time and space. Both ideas give the same answers, and the prefix-sum view is the one that also works for sums over other ranges.

    Edge cases and common mistakes

    • All numbers negative. For [-4, -1, -7] the prefix sums are -4, -5 and -12. The best run is the single element -1, and the function returns -1. Because minSum is updated after result, the empty run never wins with a sum of 0.
    • Updating minSum too early. On the same input, that order makes partialSum - minSum equal 0 at the first element, and the function would return 0.
    • Starting result at 0. This fails for the same all-negative inputs.
    • Forgetting the empty prefix. If minSum started at a large number, a run beginning at index 0 could never be found. For [3, 4] the answer 7 needs the prefix sum 0.
    • A single element. [5] returns 5.

    Testing

    • [-2, -5, 6, -2, -3, 1, 5, -6] gives 7.
    • [-4, -1, -7] gives -1.
    • [3, -10, 4] gives 4.
    • [5] 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