In this article, you will learn how to find the maximum subarray sum. In other words, we need to find the contiguous array elements that provide us the maximum sum given an array.
Consider the following example to understand the concept.
Array = [-2, 1, 4, -5, -1, 4, -1, 5] Maximum subarray sum = 8
If all array elements are non-negative, then the problem becomes trivial as the maximum subarray sum will be equal to the sum of all array elements. Consider the following example.
Array = [2, 1, 0, 5, 6] Maximum subarray sum = 14
One straightforward way to calculate the maximum subarray sum is to use the brute force approach. Here, we find the maximum sum using all possible combinations. Here, we iterate over every element of an array. For each item arr[i], we calculate the sum of elements starting from arr[i] iteratively. We compare each sum with the maximum sum. If it is greater, we update the maximum sum. Otherwise, it remains unchanged.
import math def maxSubArray(arr): maximum = -math.inf for i in range(0, len(arr)): sum=0 for j in range(i, len(arr)): sum += arr[j] maximum = max(sum, maximum) #compare the resulting sum with the existing maximum value return maximum array = [-2, 1, 4, -5, -1, 4, -1, 5] max_sum = maxSubArray(array) print("Maximum subarray sum:", max_sum)
Maximum subarray sum: 8
Even though the approach is simple, it is computationally expensive and has a time complexity of O(n2), where n is the array length. Other solutions exist, such as the divide and conquer approach and Kadane’s algorithm, which are more efficient than the brute force technique.