What is Kadane's Algorithm?

Kadane's Algorithm is a dynamic programming approach to find the contiguous subarray within a one-dimensional array of numbers that has the largest sum. It runs in O(n) time complexity.

How does Kadane's Algorithm work?

The algorithm iterates through the array, keeping track of the maximum sum of a subarray ending at the current position (max_ending_here) and the overall maximum sum found so far (max_so_far). At each position, it decides whether to extend the existing subarray or start a new one.

Dynamic Programming

Kadane's Algorithm

An elegant and efficient O(n) solution to the classic Maximum Subarray Sum problem. This guide breaks down the logic and implementation for your coding interviews.

Maximum Subarray Sum

Kadane's algorithm is a simple yet powerful way to find the maximum sum of a contiguous subarray. It's a must-know for any coding interview.

                            function maxSubArray(nums) {
                            let maxSoFar = nums[0];
                            let maxEndingHere = nums[0];
                            
                            for (let i = 1; i < nums.length; i++) {
                            maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
                            maxSoFar = Math.max(maxSoFar, maxEndingHere);
                            }
                            
                            return maxSoFar;
                            }
                        

AI Coach Hint: The core idea of Kadane's algorithm is the choice at each step: either start a new subarray at the current element or extend the previous subarray. If the `max_ending_here` becomes negative, it's better to start fresh from the next element.