Maximum Subarray

Statement

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

Examples

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
→ 6                  ([4, -1, 2, 1])

nums = [1]
→ 1

nums = [5, 4, -1, 7, 8]
→ 23                 (the whole array)

nums = [-3, -1, -2]
→ -1                 (must be non-empty; the best single element wins)

Constraints

• 1 ≤ len(nums) ≤ 10⁵
• -10⁴ ≤ nums[i] ≤ 10⁴
• The subarray must be contiguous and non-empty. The all-negative case is allowed and the answer is the largest (least negative) element.

What this problem is really testing

Whether you can spot an "extend or restart" structure and write a one-pass O(n) algorithm with O(1) memory. The brute force is obvious: every (l, r) pair is a candidate, with O(n³) naive sums or O(n²) using a running total. Kadane's algorithm shows that once you reframe the problem as "best subarray ending at index i", the whole optimisation collapses into a single line of state. The interviewer is checking whether you reach for that reframe, not whether you can recite the algorithm.