Maximum Subarray — Blind 75 practice

Problem

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

Examples

Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6

Example 2:
Input: nums = [1]
Output: 1

Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23

Constraints

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

Prerequisites

Greedy arguments — and the habit of asking what would have to be true for the local choice to be safe, before trusting it.

How to think about it

1. Kadane: Extend or Restart Optimal

Intuition

At each element there is one question: is the run so far helping? If the total behind you is negative it is dead weight, and starting fresh at this element beats carrying it. That single decision — extend or restart — is Kadane's algorithm, and the running best is recorded separately so a later decline cannot erase an earlier peak.

Algorithm

1. Start both the running total and the best at the first element.
2. For each next element, take the larger of the element alone and the element plus the running total.
3. Update the best with the running total.

Time & Space

Time O(n). Space O(1). The divide-and-conquer version is O(n log n) and worth naming as the follow-up.