Maximum subarray problem - Kadane's Algorithm

In this programming tutorial we will try to solve maximum subarray problem using Kadane's algorithm.

Related: Maximum subarray problem - simple approach.

Problem statement

Given an array of N numbers (positive, negative or zero) find the sum of the largest contiguous subarray.

Input:

[1, 2, 4, -3]

Solution

We will find the sum of the largest contiguous subarray using Kadane's Algorithm by calculating the maximum sum at a given position by using the maximum sum at a previous position.

Steps:

1. Set max_sum = -1e18 (or set to some higher negative value like -INFINITY), current_sum = 0
2. Loop through each element of the array
   1. current_sum += ith element of the array
   2. if current_sum > max_sum
      • then, max_sum = current_sum
   3. if current_sum < 0
      • then, current_sum = 0

Calculation

+---------------+---------+
| Variables     | Sum     |
+---------------+---------+
| current_sum   | 0       |
| max_sum       | -1e18   |
+---------------+---------+
| i = 0         |         |
| array[i] = 1  |         |
| current_sum   | 1       |
| max_sum       | 1       |
+---------------+---------+
| i = 1         |         |
| array[i] = 2  |         |
| current_sum   | 3       |
| max_sum       | 3       |
+---------------+---------+
| i = 2         |         |
| array[i] = 4  |         |
| current_sum   | 7       |
| max_sum       | 7       |
+---------------+---------+
| i = 3         |         |
| array[i] = -3 |         |
| current_sum   | 4       |
| max_sum       | 7       |
+---------------+---------+

Code

Python

numbers = [1, 2, 4, -3]
n = len(numbers)
max_sum = -1e18
current_sum = 0

for i in range(n):
    current_sum += numbers[i]
    if current_sum > max_sum:
        max_sum = current_sum
    if current_sum < 0:
        current_sum = 0

print(max_sum)

Output

7

Time complexity

Time complexity for this is O(n) which is better than the one we saw in the simple approach which had O(n2).