Pattern Recognition Drill

#3 — Max subarray sum (Kadane's)

Medium Arrays & Strings

The Problem

Given array a, find the contiguous subarray with the largest sum.

What approach would you use?

Think about it before scrolling down.

Key Signals

Dynamic Programming

Kadane's: dp[i] = max(a[i], dp[i-1]+a[i]). Decide at each element: extend or restart. O(n).

Alt: Divide & Conquer

Split array, solve halves, check cross-boundary max. O(n log n) — correct but slower.

Common Trap

Brute force checking all subarrays is O(n²) or O(n³). The 'extend or restart' insight is key.

← #2 #4 →