Pattern Recognition Drill
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.
Kadane's: dp[i] = max(a[i], dp[i-1]+a[i]). Decide at each element: extend or restart. O(n).
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.