Maximum Subarray
Domain: Algorithms
🎯 Motivation
Find the contiguous subarray with the largest sum. Kadane’s algorithm solves it in O(n) using DP.
📋 Concrete Example
Array [-2, 1, -3, 4, -1, 2, 1, -5, 4]. Max subarray is [4, -1, 2, 1] with sum 6. Kadane tracks the best ending at each position.
🔗 Analogy
Finding the most profitable streak in a stock price history. You want the longest consecutive period where the total gain is maximised.