Maximum subarray problem

Programming

Share

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

Share