Kadane's Algorithm
Learn Kadane's Algorithm (Arrays, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Maximum Subarray Sum in O(n) Kadane's Algorithm finds the maximum-sum contiguous subarray in a single pass. The insight: at each index, a running sum either extends the previous subarray or restarts from the current element - whichever gives a bigger sum. currentSum = Math.max(arr[i], currentSum + arr[i]) maxSum = Math.max(maxSum, currentSum) If currentSum ever drops below arr[i] itself, it's better to abandon the old subarray and start fresh at i .