70 · Maximum Subarray

In an Xcode test target:

import Testing

struct MaximumSubarrayTests {

    @Test(arguments: [
        ([-3, 4, -1, 2, -5, 3], 5),
        ([-4, -2, -7], -2),
        ([7], 7),
    ])
    func returnsTheLargestSumOfAConsecutiveRun(numbers: [Int], expected: Int) {
        #expect(maxSubArray(numbers) == expected)
    }

    // MARK: - Privates
    private func maxSubArray(_ numbers: [Int]) -> Int {
        0
    }
}

In a playground:

func maxSubArray(_ numbers: [Int]) -> Int {
    0 // your solution
}

let cases: [([Int], Int)] = [
    ([-3, 4, -1, 2, -5, 3], 5),
    ([-4, -2, -7], -2),
    ([7], 7),
]
for (numbers, expected) in cases {
    let got = maxSubArray(numbers)
    print(got == expected ? "PASS" : "FAIL", numbers, "→", got, "expected", expected)
}

Greedy running best — Kadane's algorithm. The cue is "largest sum" of a consecutive run, with negatives allowed. At each number, the best run that ends right there either continues the best run that ended one step earlier, or starts fresh at this number — whichever is bigger.

Walk along the list carrying one number: the best total of a run that ends at the current position. For each new number, ask whether the run so far helps or hurts. If the run so far has a positive total, adding the new number to it beats starting over; if its total is negative or zero, it only drags things down, so drop it and start a new run at this number. Keep a second number for the best total seen anywhere, and update it after every step.

Time O(n): one pass with constant work per number. Space O(1): two variables.

func maxSubArray(_ numbers: [Int]) -> Int {
    var current = numbers[0]
    var best = numbers[0]
    for number in numbers.dropFirst() {
        current = max(number, current + number)  // extend the run, or start over here
        best = max(best, current)
    }
    return best
}

Both variables start at the first number, not at 0. Starting best at 0 is the classic bug: it reports 0 for [-4, -2, -7], a total no non-empty run has.

Verified with swift test on Swift 6.4 in Swift 6 mode: the three examples above, four more (a single zero, all positive, a big negative between two positives, a value near Int.min that would trap with an Int.min start), and 3,000 random lists checked against a brute force that adds up every run.

[-3, 4, -1, 2, -5, 3]

Answer 5, the run 4, -1, 2. At the 4, the run so far (−3) only hurts, so the run restarts.

[-4, -2, -7] — current goes −4, then max(−2, −6) = −2, then max(−7, −9) = −7. Best stays at −2.

Starting from Int.min crashes instead of being wrong. A common way to "handle all negatives" is var current = Int.min, best = Int.min and then loop over every number. The first step computes current + number = Int.min + (-4), which is below the smallest Int. In C or Java that silently wraps to a huge positive number; Swift checks every arithmetic operation and stops the program with an overflow error. Start both values at numbers[0] and loop over dropFirst(), as above — that needs no sentinel at all. (The wrapping operator &+ exists, but wrapping here would give a wrong answer, not a right one.)

• "Return where the run starts and ends." → Track a start index that resets to i whenever you restart, and copy it with i into bestStart, bestEnd whenever best improves.
• "Do it with divide and conquer." → Best run is in the left half, the right half, or crosses the middle (best suffix of the left + best prefix of the right). O(n log n) — worse than Kadane, but it's the follow-up some interviewers want.
• "Largest product instead of sum." → A negative times a negative flips sign, so carry both the largest and the smallest product ending here; at each number, the new largest is the max of the number, largest × number and smallest × number.