Kadane’s Algorithm¶

An efficient technique used to find the maximum sum of a contiguous subarray within a given array of numbers. Its beauty lies in its simplicity and its ability to solve the maximum subarray sum problem in linear time complexity $\(\text{O}(n)\)$

Algorithm¶

The algorithm works by maintaining two variables:

1. max_ending_here: the maximum sum contiguous subarray ending at the current position.
2. max_so_far: the maximum sum of contiguous subarray found so far.

The key insight is that maximum subarray ending at each position is either:

• The current element itself, or
• The current element plus the maximum subarray ending at the previous position

Steps¶

1. Initialize both max_ending_here and max_so_far with the first element of the array.
2. Iterate through the array starting from the second element:
3. For each element, update max_ending_here:
4. If adding the current element to max_ending_here results in a larger sum, keep the sum.
5. Otherwise, start a new subarray from the current element.
6. Update max_so_far if max_ending_here is greater.
7. After the iteration, max_so_far will contain the maximum subarray sum.

Code ¶

Complexity¶

Time complexity: O(n), we make only one iterations through the array.\ Space complexity: O(1), only two variables.

Practice Problems¶

Reference ¶

• Kadane’s Algorithm: Mastering the Maximum Subarray Problem

\ \

Comments