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:

   • If adding the current element to max_ending_here results in a larger sum, keep the sum.

   • Otherwise, start a new subarray from the current element.

4. Update max_so_far if max_ending_here is greater.

5. 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

Name	Level	Link
Maximum Product Subarray
Maximum Sum Increasing Subsequence (MSIS)
Longest Continuous Increasing Subsequence (LCIS)
Max Consecutive ones.
Maximum Circular Subarray Sum
Maximum Sum Rectangle
Largest Sum Contiguous Subarray with at least K numbers
Flip Bits

Reference

• Kadane’s Algorithm: Mastering the Maximum Subarray Problem