Maximum Subarray Solution

Problem

Given an integer array, find the contiguous non-empty subarray with the largest sum and return that sum.

Approach

Use Kadane's algorithm. At each position, the best subarray ending there either extends the best subarray ending at the previous position or starts fresh at the current number.

So the running sum becomes the larger of the current number and the running sum plus the current number. Track the best running sum seen.

Starting from the first element, rather than from zero, keeps the answer correct when every number is negative.

Solution

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        best = current = nums[0]

        for num in nums[1:]:
            current = max(num, current + num)
            best = max(best, current)

        return best

Complexity

Time: O(n).
Space: O(1).

Edge cases

All negative numbers: the answer is the largest single number.
A single element returns itself.
A divide and conquer solution also exists at O(n log n), but Kadane is simpler and faster.