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.

Implementation

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)

Output

Maximum subarray sum: 8

Even though the approach is simple, it is computationally expensive and has a time complexity of O(n²), 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.