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

# Reference

• Kadane’s Algorithm: Mastering the Maximum Subarray Problem

\