How would you find the maximum subarray sum?

Finding the maximum subarray sum is a common algorithmic problem that can be solved using algorithms such as Kadane’s algorithm. Before we get into that, let’s understand what is a subarray. A subarray is a contiguous part of an array. Hence, in the problem, we are looking for a contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Let’s discuss how Kadane’s algorithm works:

1. Initialize:

- max_so_far = 0

- max_ending_here = 0

2. Loop over each element of the array (Let the current element in loop be ’x’)

- max_ending_here = max_ending_here + x

- if max_ending_here < 0 max_ending_here = 0

- if max_so_far < max_ending_here max_so_far = max_ending_here

3. return max_so_far

In the algorithm, max_so_far stores the maximum subarray sum encountered so far. And, max_ending_here stores the sum of the current subarray. If at some point in time, we get max_ending_here < 0, we start looking for a new subarray - as the current subarray ends.

In terms of time complexity, this algorithm runs in O(N) where N is the number of elements in the input array. This is because Kadane’s algorithm needs just one loop through the array, so it is quite time efficient.

Here is an example code snippet in Python:

def max_subarray_sum(arr):
  size = len(arr)
  
  max_so_far = max_ending_here = 0
  
  for i in range(0, size):
    max_ending_here = max_ending_here + arr[i]
    
    if max_ending_here < 0:
      max_ending_here = 0
      
    if max_so_far < max_ending_here:
      max_so_far = max_ending_here
      
  return max_so_far

Now, to demonstrate its working let’s consider ‘arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]‘

Loop through the array and on each iteration;

- add the current element to max_ending_here, ‘-2‘ at i=0.

- Then compare this sum with 0. If it is less than 0, reset max_ending_here to 0. So in the first iteration with ‘-2‘, max_ending_here becomes 0

- Then compare max_so_far with max_ending_here, if
max_ending_here is greater, replace max_so_far with it.

- Run this loop for the length of the array and at the end, max_so_far will hold the maximum sum.

After going through all the elements in the array, we’ll end up with max_so_far = ‘6‘, which indeed is the maximum sum subarray ‘[4, -1, 2, 1]‘.