Start learning free

LESSON 232 OF 415 · FREE CODING INTERVIEW QUESTIONS

Maximum Sum Subarray in Swift: O(n²) Brute Force with a Running Sum

Practice O(n2) Read the full explanation

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^2) time and use O(1) extra space.




Let's come up with a brute force approach. Brute force tries each and every candidate to our solution. For this problem, the candidates are all the subarrays of nums. How can we try out each subarray?

A subarray is defined by its left endpoint, let's name it index i and its right point, let's name it index j. We should go through each pair of indices (i, j) such that 0 <= i <= j < n, where n is the length of nums. How can we achieve this?

Using two nested for loops! The first loop will try out each possible i between 0 and n - 1. The second loop will be written inside the first one and will try out each possible j between i and n - 1. 
for each i : 0 to n - 1:
		for each j : i to n - 1:
We will use a variable maxSum to store the greatest sum found so far and for each pair (i, j), update maxSum with sum(nums[i...j]) if it's the case: 
maxSum = nums[0]
for each i : 0 to n - 1:
	for each j : i to n - 1:
		maxSum = max(maxSum, sum(nums[i...j]))
return maxSum
All we have to do now is find a way of getting sum(nums[i...j]) in O(1) time. How can we do this?

One way is using Partial Sums. But that implies using an extra array, which takes O(n) extra space. There is a better way. We can use a variable sum to store the sum of the current subarray sum(nums[i...j]). 
maxSum = nums[0]
for each i : 0 to n - 1:
	for each j : i to n - 1:
		maxSum = max(maxSum, sum)
return maxSum
How should we update this variable throught the algorithm to make sure that it always stores the correct sum?

Each time we increment j in the second loop, we should add nums[j] to sum. Also, each time we increment i in the first loop, we start with a new empty subarray so we should reset sum to 0: 
maxSum = nums[0]
for each i : 0 to n - 1:
	sum = 0
	for each j : i to n - 1:
		sum += nums[j]
		maxSum = max(maxSum, sum)
return maxSum

STEP 1 OF 7
    Ctrl + Enter to check

    SWIFT · FREE CODING INTERVIEW QUESTIONS

    Maximum Sum Subarray in Swift, explained

    Problem overview

    The method maxSumSubarray receives an array of integers, nums, which may hold both positive and negative values. It returns the largest sum that any continuous run of elements can have. The run must be unbroken, so you can't skip elements in the middle.

    For nums = [-2, -5, 6, -2, -3, 1, 5, -6] the answer is 7, the sum of [6, -2, -3, 1, 5]. The statement allows O(n²) time and O(1) extra space.

    Approach: try every subarray, but add one element at a time

    A subarray is fixed by its first index i and its last index j, with i <= j. The brute-force idea is to try every such pair and keep the best sum. There are about n²/2 pairs.

    The naive version adds up nums[i] through nums[j] for each pair, which costs another loop and makes the total O(n³). The fix is to notice that for a fixed i, moving j one step to the right just adds one element. A running sum that starts at 0 for each new i and grows by nums[j] gives every subarray sum in constant time. That brings the total to O(n²), and the only extra memory is a few integers.

    Take i = 2 in the example. As j goes from 2 to 7, the running sums are 6, 4, 1, 2, 7, 1. The best of these is 7, which is also the best over all pairs.

    Other lessons on this problem make it faster, down to a single pass. This one is the plain version and is the right place to see why the problem is hard to do cheaply.

    Step by step

    1. Declare maxSum as nums[0]. Do not start at 0. If every number is negative, the best subarray has a negative sum, and a starting 0 would never be beaten. nums[0] is itself a subarray, so it is a safe starting answer.
    2. Loop over the first index. for i in 0..<nums.count visits every possible start. The half-open range 0..<n stops before n.
    3. Declare var sum = 0 inside this loop. It is reset for every new start, which means "an empty subarray so far", and it is not needed outside the loop.
    4. Loop over the last index. for j in i..<nums.count starts at i, so the subarray holds at least one element and the last index is never before the first.
    5. Add nums[j] to sum. Now sum is exactly the sum of nums[i...j].
    6. Update the best. maxSum = max(maxSum, sum) keeps the larger of the two in one line.
    7. Return maxSum after both loops finish.

    The solution in Swift

    class Solution {
    func maxSumSubarray(_ nums: [Int]) -> Int {
        var maxSum = nums[0]
        for i in 0..<nums.count {
            var sum = 0
            for j in i..<nums.count {
                sum += nums[j]
                maxSum = max(maxSum, sum)
            }
        }
        return maxSum
    }
}

    Swift details worth knowing:

    • Ranges. 0..<n excludes n, and 0...n includes it. Here the half-open form matches array indices, which run from 0 to count - 1.
    • Inner ranges can't run backwards. i..<nums.count is only valid while i <= nums.count. Swift stops with a run-time error for a range whose lower bound is greater than its upper bound. Because i is always less than nums.count inside the outer loop, this never happens.
    • The global max. max(a, b) is a free function from Swift's standard library, so it needs no import and no receiver.
    • Naming a variable sum is fine. Swift has no global function called sum. Arrays do have reduce, which could add elements, but the loop keeps the memory constant and shows the idea.
    • Overflow traps. Int is 64 bits in Swift, and arithmetic that overflows stops the program instead of wrapping. Ordinary inputs are nowhere near that limit.
    • Empty arrays. nums[0] on an empty array crashes the program at run time, so this solution assumes at least one element.

    Calling it:

    let solution = Solution()
print(solution.maxSumSubarray([-2, -5, 6, -2, -3, 1, 5, -6]))
print(solution.maxSumSubarray([-3, -1, -2]))
print(solution.maxSumSubarray([1, 2, 3]))

    7
-1
6

    Complexity

    Time: O(n²). The outer loop runs n times, and for index i the inner loop runs n - i times. That adds up to n(n + 1)/2 steps, each with constant work.

    Space: O(1). The code keeps only maxSum, sum and the two loop indices.

    Edge cases and common mistakes

    • All negative numbers. [-3, -1, -2] returns -1, the single best element. Starting maxSum at 0 would wrongly return 0, which is the sum of no elements.
    • A single element. [5] returns 5, since the loops visit exactly one pair.
    • All positive numbers. The whole array wins: [1, 2, 3] returns 6.
    • Declaring sum outside the outer loop. The sums of earlier starts would leak into later ones, and the subarrays would no longer be contiguous.
    • Starting j at 0. That would add elements before i and break the meaning of the pair.
    • Updating maxSum outside the inner loop. Only the sum of the longest subarray from each i would be compared, and shorter ones, which may be better, would be skipped.

    Testing

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