# Maximum Subarray

- **Canonical ID**: `maximum-subarray`
- **Canonical URL**: https://dsacheatsheet.com/problems/maximum-subarray
- **Difficulty**: medium
- **Patterns**: 1D DP, Arrays
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/maximum-subarray/

## 1. Core Invariant / The Trick

Kadane’s Algorithm: any negative running prefix sum only lowers subsequent subarrays. Either extend the current subarray (`cur + x`) or start fresh at `x`: `cur = max(x, cur + x)`, `best = max(best, cur)`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: Optimal subarray ending at index `i` depends solely on `max(0, dp[i-1]) + nums[i]`, executing in one O(1)-space pass.

## 3. Minimal Idiomatic Code

### Python
```python
def maxSubArray(nums: list[int]) -> int:
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best
```

### TypeScript
```typescript
export function maxSubArray(nums: number[]): number {
  let best = nums[0], cur = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);
    best = Math.max(best, cur);
  }
  return best;
}
```

### C++
```cpp
int maxSubArray(vector<int>& nums) {
    int best = nums[0], cur = nums[0];
    for (size_t i = 1; i < nums.size(); ++i) {
        cur = max(nums[i], cur + nums[i]);
        best = max(best, cur);
    }
    return best;
}
```

### Java
```java
int maxSubArray(int[] nums) {
    int best = nums[0], cur = nums[0];
    for (int i = 1; i < nums.length; i++) {
        cur = Math.max(nums[i], cur + nums[i]);
        best = Math.max(best, cur);
    }
    return best;
}
```

### Go
```go
func maxSubArray(nums []int) int {
    best, cur := nums[0], nums[0]
    for _, x := range nums[1:] {
        cur = max(x, cur+x)
        best = max(best, cur)
    }
    return best
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Initializing `best = 0` breaks on all-negative inputs (`[-5, -2, -8]` should return `-2`, not `0`). Initialize `best = cur = nums[0]`.

### Follow-ups
- Divide and conquer in O(N log N) returns `(total, bestPrefix, bestSuffix, bestSub)` per segment (enables MapReduce / segment trees for range queries).