Kadane's algorithm

December 10, 2023

Kadane’s algorithm is a dynamic programming approach used to find the maximum sum of a contiguous subarray within a one-dimensional array of numbers. It’s renowned for its efficiency, solving the problem in ( O(n) ) time, where ( n ) is the number of elements in the array. Here’s a breakdown of how it works:

Basic Idea #

Kadane’s algorithm iterates through the array, calculating the maximum subarray sum ending at each position. It does this by keeping track of the following:

1. Current Maximum Ending Here: This is the maximum sum of a subarray ending at the current position.
2. Global Maximum So Far: The highest sum found across all subarrays checked up to the current point.

Process #

1. Initialization: Start by setting both the current maximum and the global maximum to the first element of the array.

2. Iteration: For each element in the array (except the first one), do the following:

   • Update Current Maximum: The new current maximum is either the current element itself or the sum of the current element and the previous current maximum (whichever is larger). This step effectively decides whether to extend the previous subarray to include the current element or start a new subarray from the current element.
   • Update Global Maximum: If the new current maximum is greater than the global maximum, update the global maximum.

3. Result: After iterating through the array, the global maximum holds the maximum sum of any subarray within the array.

Key Points #

• Efficiency: The algorithm only needs to make a single pass through the array, giving it ( O(n) ) time complexity.
• Handling Negative Numbers: The algorithm can handle arrays with negative numbers. Even if all numbers are negative, it finds the ’least negative’ number as the maximum sum.
• Empty Subarray: If an empty subarray (sum of 0) is considered a valid subarray with the maximum sum, a small modification is needed in the algorithm to handle arrays with all negative numbers.

Example #

Consider an array [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

• The algorithm starts with -2.
• Then it compares -2 with -2 + 1, and takes 1 (starting a new subarray).
• It continues this process, at each step deciding whether to add the current element to the existing subarray or start a new subarray.
• The global maximum gets updated whenever a new larger sum is found.

By the end of the array, the global maximum will hold the value of the maximum subarray sum, which in this case is 6 (subarray [4, -1, 2, 1]).

Kadane’s algorithm is a classic example of a simple yet efficient dynamic programming approach.

Note #

Generated by ChatGPT