Maximum Subarray

Fibonacci Number

Contains Duplicate

Return the largest sum obtainable from a non-empty contiguous subarray.

Given an integer array `nums`, return the maximum sum of any non-empty contiguous subarray.

**Input / output**
- Input: `nums: integer[]`
- Output: integer maximum sum

**Examples**
1. `[-2,1,-3,4,-1,2,1,-5,4]` returns `6` from `[4,-1,2,1]`.
2. `[-5,-2,-8]` returns `-2`; choosing no elements is not allowed.

**Constraints**
- `1 <= nums.length <= 100,000`
- `-10,000 <= nums[i] <= 10,000`

**Follow-up**
Can you derive Kadane's algorithm from the choice to extend the previous subarray or start a new one?

- 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.