Find the contiguous subarray with the largest sum and return that sum.

Interview question: Maximum Subarray

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return that sum.

- We need the largest possible sum from one contiguous subarray.
- The subarray must contain at least one number.
- Negative numbers matter because the best answer could be a single negative element.

Understand the Problem

- Try every possible start and end index.
- Compute each subarray sum and keep the largest.
- This is correct but inefficient because there are O(n²) subarrays.

Start with a Brute Force Idea

- At each number, decide whether to extend the previous subarray or start fresh.
- If the previous running sum is harmful, starting at the current number is better.
- Track both the best sum ending at the current index and the best sum seen overall.

Key Insight: Keep the Best Ending Here

- Initialize both values with the first element.
- For every next number, update `current` to the better of starting new or extending.
- Then update `best` with the larger value.

Apply Kadane's Algorithm

- Kadane's algorithm scans the array once.
- Time complexity is O(n).
- Space complexity is O(1) because only two running values are stored.