Finding the maximum subarray sum sounds simple… Until you try brute force: Check all subarrays → O(n²) But what if you could solve it in O(n)? That’s exactly what Kadane’s Algorithm does. Core Idea At every index, you make a decision: Start a new subarray OR extend the previous one Whichever gives a larger sum. Implementation public static int maxSubarraySum(int[] arr) { int maxSoFar = arr[0]; int maxEndingHere = arr[0]; for (int i = 1; i < arr.length; i++) { maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]); maxSoFar = Math.max(maxSoFar, maxEndingHere); } return maxSoFar; Enter fullscreen mode Exit fullscreen mode } Example Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4] Best subarray: [4, -1, 2, 1] → sum = 6 Why It Works Negative sum hurts future results So we drop it and start fresh Positive sum helps → we extend it The Real Insight Kadane is about making a local decision that leads to a global optimum Key Insights Tracks current max and global max Works with negative numbers No extra space required For…