## What is it? Kadane's Algorithm finds the maximum sum contiguous subarray of a given array in O(n) time. It handles arrays with negative numbers by deciding at each step whether to extend the current subarray or start fresh. ## How it works - Initialize `maxSum = arr[0]`, `currentSum = arr[0]` - For each element from index 1: - `currentSum = max(arr[i], currentSum + arr[i])` - If `currentSum + arr[i] < arr[i]`, starting fresh at `arr[i]` is better - `maxSum = max(maxSum, currentSum)` - Return `maxSum` ## When to use - Maximum subarray sum (LeetCode 53) - As a building block for Maximum Product Subarray, Circular Max Subarray - Any problem involving "best contiguous segment" ## Key Points - O(n) time, O(1) space — optimal - Works correctly when all elements are negative (returns the largest single element) - The decision at each step: "is the current element alone better than extending the previous subarray?"