Maximum Subarray

Given an array of integers nums, find the subarray with the largest sum and return the sum.

A subarray is a contiguous non-empty sequence of elements within an array.

The subarray [4,-2,2,1,-1,4] has the largest sum 8.

Approach

Use Kadane's algorithm. Track the best subarray sum ending at the current index and the global maximum. At each step, either extend the previous subarray or start fresh at the current number.

Why It Works

Any maximum subarray ending at index i is either the current element alone or the previous best ending at i-1 plus the current element. Taking the max of these at each step yields the best ending here, and the global max over all endings is the answer.

Complexity

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

Reference Implementation (Python)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        best = nums[0]
        current = nums[0]
        for num in nums[1:]:
            current = max(num, current + num)
            best = max(best, current)
        return best