LESSON 233 OF 415 · PARTIAL SUMS #1

Maximum Sum Subarray in Swift: Kadane's Algorithm in O(n) Time

( Kadane's Algorithm )

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 O(1) extra space.

STEP 1 OF 6

Guided

Ctrl + Enter to check

SWIFT · PARTIAL SUMS #1

Maximum Sum Subarray in Swift, explained

Problem overview

The method maxSumSubarray receives an array of integers that may hold both positive and negative values. It must return the largest sum that a continuous run of elements can have. The run must contain at least one element.

For nums = [-2, -5, 6, -2, -3, 1, 5, -6] the best run is [6, -2, -3, 1, 5], and its sum is 7. No other run of neighbouring elements adds up to more.

The statement asks for O(n) time and O(1) extra space. That means one pass over the array, with a fixed number of variables and no extra array.

Approach: the best run that ends here

Checking every start and end is the brute-force way, and it costs at least O(n²). Kadane's algorithm gets to O(n) by asking a smaller question at each position: what is the best sum of a run that ends at this element?

That run either extends the best run ending at the previous element, or it starts fresh with just the current element. Which of the two is better depends on one thing: whether the previous best sum is positive. A positive sum helps the new element, so keep it. A negative sum only drags it down, so throw it away and start over. In symbols:

maxSum = val + max(maxSum, 0)

The overall answer is the largest of those "best sum ending here" values over the whole array, because the best run has to end somewhere.

Here is the idea on the example. Each row shows the element, the best sum ending there, and the best answer so far:

val	maxSum	result
-2	-2	-2
-5	-5	-2
6	6	6
-2	4	6
-3	1	6
1	2	6
5	7	7
-6	1	7

At the element 6 the running sum was negative (-5), so the run restarts and maxSum becomes 6. After that the run keeps growing through -2, -3, 1 and 5, and it reaches 7. The final -6 shrinks the running sum, but result keeps the 7.

Step by step

Create result from the first element. It holds the best sum found so far. Starting it at 0 would be wrong: if every number is negative, the right answer is negative, and 0 would hide it. The first element is a valid run by itself, so it is a safe starting value.
Create maxSum at 0. It is the best sum of a run ending at the current position. Before any element is read, the "run" is empty and its sum is 0.
Loop over the elements with a for loop, naming each one val.
Update maxSum with the recurrence: add val to the larger of the old maxSum and 0. Taking the larger of the two is the "extend or restart" decision.
Update result with max, so it never falls behind the best run seen at any position.
Return result once the loop is done.

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
    }
}

A few Swift details:

The unlabeled parameter. The _ before nums means a caller writes maxSumSubarray([1, 2]) without a label.
var for values that change. Both result and maxSum are reassigned inside the loop, so they must be var. The compiler would reject an assignment to a let constant. The loop variable val is a new constant for every pass.
Global max. Swift's max(a, b) is a free function that works on any two comparable values, so it is called without a receiver.
Type inference. nums[0] is an Int, so result is an Int, and so is maxSum, since it starts as the literal 0 and the loop adds Int values to it.
Arithmetic traps on overflow. Int is 64 bits, and a sum that goes past that range stops the program with a run-time error rather than wrapping around. For ordinary inputs this never matters.
Empty arrays. nums[0] on an empty array crashes at run time. The lesson's tests always give at least one element.

Complexity

Time: O(n). The loop visits each element once and does a constant amount of work for each.

Space: O(1). Only result, maxSum and the loop variable are used, no matter how long the array is.

Edge cases and common mistakes

All numbers negative. [-4, -1, -7] returns -1, the largest single element. Starting result at 0 would return 0, which is not the sum of any run.
A single element. [5] returns 5.
A run that is best on its own. [3, -10, 4] returns 4: the -10 makes the running sum negative, so the 4 starts fresh, but 4 is still bigger than the 3 at the start.
Taking the whole array. Adding every positive number is not the answer. A negative number in the middle can cost more than the positives after it give back.
Restarting at the wrong moment. Using max(maxSum, 0) restarts only when the previous sum is below 0. A previous sum of exactly 0 changes nothing either way.
Forgetting to update result inside the loop. maxSum at the end of the loop is the best run ending at the last element only, not the best run overall.

Testing

[-2, -5, 6, -2, -3, 1, 5, -6] gives 7.
[-4, -1, -7] gives -1.
[5] gives 5.
[3, -10, 4] gives 4.

Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free