# LeetCode 53: Maximum Subarray

## Problem Restatement

We are given an integer array `nums`.

We need to find the contiguous subarray with the largest possible sum and return that sum.

A subarray means a continuous part of the array. We cannot skip elements.

The official problem asks for the largest subarray sum, not the subarray itself. The constraints are `1 <= nums.length <= 10^5` and `-10^4 <= nums[i] <= 10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | The maximum sum of any non-empty contiguous subarray |
| Subarray rule | Elements must be consecutive |
| Empty subarray | Not allowed |

Function shape:

```python
def maxSubArray(nums: list[int]) -> int:
    ...
```

## Examples

For:

```python
nums = [-2,1,-3,4,-1,2,1,-5,4]
```

The best subarray is:

```python
[4, -1, 2, 1]
```

Its sum is:

```python
4 + (-1) + 2 + 1 = 6
```

So the answer is:

```python
6
```

For:

```python
nums = [1]
```

The only non-empty subarray is `[1]`, so the answer is:

```python
1
```

For:

```python
nums = [5,4,-1,7,8]
```

The best subarray is the entire array:

```python
[5, 4, -1, 7, 8]
```

The answer is:

```python
23
```

## First Thought: Brute Force

The simplest approach is to try every possible subarray.

Choose a start index `i`.

Then extend the subarray to every end index `j`.

While extending, keep a running sum.

```python
class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        best = nums[0]
        n = len(nums)

        for i in range(n):
            total = 0

            for j in range(i, n):
                total += nums[j]
                best = max(best, total)

        return best
```

This checks all contiguous subarrays and records the largest sum.

## Problem With Brute Force

There are many subarrays.

For an array of length `n`, the number of possible start and end pairs is about `n^2`.

So this solution takes:

```python
O(n^2)
```

The constraint allows up to `10^5` elements, so quadratic time is too slow.

We need a linear solution.

## Key Insight

At each index, ask one question:

Should the best subarray ending here extend the previous subarray, or should it start fresh here?

For a number `num`, there are only two choices:

```python
current + num
```

or:

```python
num
```

If the previous running sum helps us, we keep it.

If the previous running sum hurts us, we discard it and start a new subarray at the current number.

This gives the recurrence:

```python
current = max(num, current + num)
```

Then the global answer is the largest `current` value seen so far.

This is Kadane's algorithm.

## Algorithm

Initialize:

```python
current = nums[0]
best = nums[0]
```

Then scan from the second element onward.

For each `num`:

1. Update `current` to the best subarray sum ending at this element.
2. Update `best` to the best subarray sum seen anywhere so far.

```python
current = max(num, current + num)
best = max(best, current)
```

At the end, return `best`.

## Correctness

Let `current` mean the maximum sum of a non-empty subarray that must end at the current index.

For the current number `num`, any subarray ending here has only two forms.

It either starts at the current index, giving sum `num`, or it extends a subarray ending at the previous index, giving sum `current + num`.

Taking the maximum of those two choices gives the best subarray ending at the current index.

The variable `best` stores the largest value of `current` seen so far. Since every non-empty subarray ends at some index, checking the best ending value at every index guarantees that `best` becomes the maximum subarray sum over the whole array.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(1)` | We keep only two variables |

## Implementation

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

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

        return best
```

## Code Explanation

We initialize both values with the first element:

```python
current = nums[0]
best = nums[0]
```

This matters because the array may contain only negative numbers.

For example:

```python
nums = [-3, -2, -5]
```

The answer should be `-2`, not `0`.

Then we process the rest of the array:

```python
for num in nums[1:]:
```

At each number, we decide whether to extend the previous subarray or start a new one:

```python
current = max(num, current + num)
```

Then we update the global answer:

```python
best = max(best, current)
```

Finally, return:

```python
return best
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) == 6
    assert s.maxSubArray([1]) == 1
    assert s.maxSubArray([5,4,-1,7,8]) == 23
    assert s.maxSubArray([-3, -2, -5]) == -2
    assert s.maxSubArray([0, 0, 0]) == 0
    assert s.maxSubArray([-1, 2, 3, -10, 4]) == 5

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[-2,1,-3,4,-1,2,1,-5,4]` | Standard example |
| `[1]` | Minimum size |
| `[5,4,-1,7,8]` | Best subarray is the whole array |
| `[-3,-2,-5]` | All numbers are negative |
| `[0,0,0]` | Neutral values |
| `[-1,2,3,-10,4]` | Best subarray appears before a large drop |