Kadane’s Algorithm: Finding the Maximum Subarray Sum

Introduction

In many problems involving arrays, we are interested in finding a subarray that gives the maximum possible sum. A subarray is a continuous part of an array.

Kadane’s Algorithm is an efficient way to solve this problem in linear time.

Problem Statement

Given an integer array arr[], find the maximum sum of a contiguous subarray.

Example 1

Input:

arr = [2, 3, -8, 7, -1, 2, 3]

Output:

11

Explanation:
The subarray [7, -1, 2, 3] has the maximum sum of 11.

Example 2

Input:

arr = [-2, -4]

Output:

-2

Explanation:
The largest element itself is the answer since all values are negative.

Kadane’s Algorithm (Efficient Approach)

• Traverse the array once

• Keep track of:

  • Current sum
  • Maximum sum so far

At each step:

• Add the current element to the running sum
• If the sum becomes negative, reset it to zero
• Update the maximum sum if needed

Python Implementation

def max_subarray_sum(arr):
    max_sum = arr[0]
    current_sum = 0

    for num in arr:
        current_sum += num

        if current_sum > max_sum:
            max_sum = current_sum

        if current_sum < 0:
            current_sum = 0

    return max_sum

# Example usage
arr = [2, 3, -8, 7, -1, 2, 3]
print(max_subarray_sum(arr))

Step-by-Step Explanation

For:

[2, 3, -8, 7, -1, 2, 3]

• Start with current_sum = 0, max_sum = 2
• Add 2 → current_sum = 2 → max = 2
• Add 3 → current_sum = 5 → max = 5
• Add -8 → current_sum = -3 → reset to 0
• Add 7 → current_sum = 7 → max = 7
• Add -1 → current_sum = 6 → max = 7
• Add 2 → current_sum = 8 → max = 8
• Add 3 → current_sum = 11 → max = 11

Final answer: 11

Key Points

• Works in a single pass
• Handles negative numbers efficiently
• One of the most important array algorithms
• Frequently asked in coding interviews

Conclusion

Kadane’s Algorithm is a powerful and efficient method to find the maximum subarray sum. It demonstrates how dynamic programming can optimize a problem from quadratic to linear time.

Understanding this algorithm is essential for mastering array-based problems and improving problem-solving skills.