Skip to main content

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 .

More lessons in Arrays