#Max Sub-array (122A)

Question. Given a 1-dimensional array, find a contiguous sub-array with the largest sum

A[1...N]: List<number>

the array we select from

The maximum sub-array can show up in 3 places:

1. The left half of $A$
2. The right half of $A$
3. The middle section of $A$

The left half and right half does not overlap. Overlap is handled by the middle section.

There are 2 base cases:

1. $A$ is empty, so we return 0 for the sum of nothing.
2. $A$ has exactly 1 element, so we return that element $A[1]$

To avoid passing the main array around on the stack, we can use the 2 pointer approach with low and high pointers. The recursive calls will look like:

function MaxSubarray():
    mid = floor((low + high) / 2)
    leftSum = MaxSubarray(low, mid)
    rightSum = MaxSubarray(mid + 1, high)
    middleSum = MaxMiddleSum(low, mid, high)

where the 2 recursive calls correspond to the left and right half of $A$.

The name is kinda misleading, but we want to consider this:

Question. What contiguous sub-array, that might contain the middle element, gives us the maximum sum?

So we check both ways. Take the element if it keeps the array contiguous AND increases the sum.

1. Check from mid - 1 to low

   // Inside MaxMiddleSum
   
   // Increases only when currLeftSum is better
   bestLeftSum = -Infinity
   // Always increases bc the sub-array need to be contiguous
   currLeftSum = 0  
   
   // for loop must go this direction
   // because the max middle sum could contain both left and right
   for i = mid - 1 to low:
   	currLeftSum += A[i]
   	if currLeftSum > bestLeftSum:
   		bestLeftSum = currLeftSum
   

   Example. Left Half

   Selecting...

   Done selecting, sum = 4

   

   

2. Then check from mid to high

   // Inside MaxMiddleSum
   bestRightSum = -Infinity
   currRightSum = 0
   
   for i = mid to high:
   	currRightSum += A[i]
   	if currRightSum > bestRightSum:
   		bestRightSum = currRightSum
   

   Example. Right Half

   Selecting...

   Done selecting, sum = 3

   

   

3. The best middle sum could also involve both the left and right half, for example if all elements are positive. So we take the max(...) of all:

   // Inside MaxMiddleSum
   return max(bestLeftSum + bestRightSum, 
              bestLeftSum,
              bestRightSum)
   

Now we know what’s max in left, right, and middle, we just take the max.

// Inside MaxSubarray
return max(leftSum, rightRum, middleSum)

function MaxMiddleSum(A[low...high], mid) -> number:
	bestLeftSum = -Infinity
	currLeftSum = 0
	
	for i = mid - 1 to low:
		currLeftSum += A[i]
		if currLeftSum > bestLeftSum:
			bestLeftSum = currSum
	
	bestRightSum = -Infinity
	currRightSum = 0
	
	for i = mid to high:
		currRightSum += A[i]
		if currRightSum > bestRightSum:
			bestRightSum = currRightSum

	return max(
		bestLeftSum + bestRightSum, 
        bestLeftSum,
        bestRightSum
	)

function MaxSubarray(A[low...high]) -> number:
	if A is empty:
		return 0 

	if low == high:
		return A[1]

	mid = floor((low + high) / 2)
	leftSum = MaxSubarray(A[low...mid])
	rightSum = MaxSubarray(A[mid + 1...high])
	middleSum = MaxMiddleSum(A[low...high], mid)

	return max(leftSum, rightSum, middleSum)

Github

Go faster: Max Subarray: Kadane’s Algorithm (WIP)