Programming
In this programming tutorial we will try to solve maximum subarray problem using simple approach.
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]
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.
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))
7
The time complexity for this is O(n2).
O(n2)