Greedy Scans: Kadane and Reach

Some greedy algorithms don't need sorting. They walk the array once and carry one or two numbers that summarise "the best so far". Two of these come up in interviews constantly.

Kadane's algorithm (maximum subarray sum). At each index, the best subarray ending here either:

• extends the best one ending at the previous index, or
• starts fresh at this element.

So cur = max(x, cur + x). The greedy rule hiding inside: if the running sum goes negative, drop it. A negative prefix can only drag down whatever comes next. The brute force checks all O(n²) subarrays; Kadane is O(n) time, O(1) space.

Reach-based jumping. Each nums[i] is the longest jump you can make from index i. Can you get to the last index?

You don't need to decide which jumps to take. Just track reach, the farthest index reachable so far. Every index up to reach is reachable (you can always jump shorter), so:

nums:   2  3  1  1  4
i=0  -> reach = max(0, 0+2) = 2
i=1  -> reach = max(2, 1+3) = 4  (last index!)

If you ever stand on an index i > reach, you're stuck: nothing before you can get you there.

Minimum number of jumps is the same idea viewed as BFS levels. With 0 jumps you cover index 0. With 1 jump you cover everything up to 0 + nums[0]. With k + 1 jumps you cover up to the farthest reach from any index in the k-jump window.

So you scan once, keep the current window's end and the farthest reach seen, and count a jump each time you walk past the window's end. You'll build this in the Jump Game II problem.