# Maximum subarray problem - Kadane's Algorithm

Programming

Share

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

### 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)`.

Share