Maximum subarray problem

In this programming tutorial we will try to solve maximum subarray problem using simple approach.

Problem statement

We are given an array of size N that consists of numbers that can be positive, negative or zero. We have to find the maximum subarray sum.

Input:

[1, 2, 4, -3]

Solution

Based on the given input array we will have the following contiguous subarrays.

Subarray of size 1:
[1], [2], [4], [-3]

Subarray of size 2:
[1, 2], [2, 4], [4, -3]

Subarray of size 3:
[1, 2, 4], [2, 4, -3]

Subarray of size 4:
[1, 2, 4, -3]

Sum of all the subarrays.

+--------------------+-----+
| Subarray           | Sum |
+--------------------+-----+
| [1]                | 1   |
+--------------------+-----+
| [2]                | 2   |
+--------------------+-----+
| [4]                | 4   |
+--------------------+-----+
| [-3]               | -3  |
+--------------------+-----+
| [1, 2]             | 3   |
+--------------------+-----+
| [2, 4]             | 6   |
+--------------------+-----+
| [4, -3]            | 1   |
+--------------------+-----+
| [1, 2, 4]          | 7   |
+--------------------+-----+
| [2, 4, -3]         | 3   |
+--------------------+-----+
| [1, 2, 4, -3]      | 4   |
+--------------------+-----+

Looking at the above table we can tell that 7 is the result.

Code

Python

def sum_of_subarray(array):
    n = len(array)
    max_sum = -1e18

    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += array[j]
            if current_sum > max_sum:
                max_sum = current_sum

    return max_sum


numbers = [1, 2, 4, -3]
print(sum_of_subarray(numbers))

Output

7

Time complexity

The time complexity for this is O(n2).