Maximum Subarray Sum linear solution

Maximum Subarray Sum aka Largest Sum Contiguous Subarray is a well-known problem in algorithm. Write an efficient program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Algorithm 1: Brute Force

The naive method is to run two loops. The outer loop picks the beginning element, the inner loop finds the maximum possible sum with first element picked by outer loop and compares this maximum with the overall maximum. Finally return the overall maximum. 

Algorithm 2: Divide and Conquer

Using Divide and Conquer approach, we can find the maximum subarray sum in O(nLogn) time. Following is the Divide and Conquer algorithm.

1) Divide the given array in two halves
2) Return the maximum of following three
….a) Maximum subarray sum in left half (Make a recursive call)
….b) Maximum subarray sum in right half (Make a recursive call)
….c) Maximum subarray sum such that the subarray crosses the midpoint

The lines 2.a and 2.b are simple recursive calls. How to find maximum subarray sum such that the subarray crosses the midpoint? We can easily find the crossing sum in linear time. The idea is simple, find the maximum sum starting from mid point and ending at some point on left of mid, then find the maximum sum starting from mid + 1 and ending with sum point on right of mid + 1. Finally, combine the two and return.

# A Divide and Conquer based program 
# for maximum subarray sum problem 
  
# Find the maximum possible sum in 
# arr[] auch that arr[m] is part of it 
def maxCrossingSum(arr, l, m, h) : 
      
    # Include elements on left of mid. 
    sm = 0; left_sum = -10000
      
    for i in range(m, l-1, -1) : 
        sm = sm + arr[i] 
          
        if (sm > left_sum) : 
            left_sum = sm 
      
      
    # Include elements on right of mid 
    sm = 0; right_sum = -1000
    for i in range(m + 1, h + 1) : 
        sm = sm + arr[i] 
          
        if (sm > right_sum) : 
            right_sum = sm 
      
  
    # Return sum of elements on left and right of mid 
    # returning only left_sum + right_sum will fail for [-2, 1] 
    return max(left_sum + right_sum, left_sum, right_sum) 
  
  
# Returns sum of maxium sum subarray in aa[l..h] 
def maxSubArraySum(arr, l, h) : 
      
    # Base Case: Only one element 
    if (l == h) : 
        return arr[l] 
  
    # Find middle point 
    m = (l + h) // 2
  
    # Return maximum of following three possible cases 
    # a) Maximum subarray sum in left half 
    # b) Maximum subarray sum in right half 
    # c) Maximum subarray sum such that the  
    #     subarray crosses the midpoint  
    return max(maxSubArraySum(arr, l, m), 
               maxSubArraySum(arr, m+1, h), 
               maxCrossingSum(arr, l, m, h)) 
              
  
# Driver Code 
arr = [2, 3, 4, 5, 7] 
n = len(arr) 
  
max_sum = maxSubArraySum(arr, 0, n-1) 
print("Maximum contiguous sum is ", max_sum) 
  
# This code is contributed by Nikita Tiwari.

Algorithm 3: Kadane’s Algorithm:

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
  (c) if(max_ending_here < 0)
            max_ending_here = 0
return max_so_far

Explanation:
Simple idea of the Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far

# Python program to find maximum contiguous subarray 
   
# Function to find the maximum contiguous subarray 
from sys import maxint 
def maxSubArraySum(a,size): 
       
    max_so_far = -maxint - 1
    max_ending_here = 0
       
    for i in range(0, size): 
        max_ending_here = max_ending_here + a[i] 
        if (max_so_far < max_ending_here): 
            max_so_far = max_ending_here 
  
        if max_ending_here < 0: 
            max_ending_here = 0   
    return max_so_far 
   
# Driver function to check the above function  
a = [-13, -3, -25, -20, -3, -16, -23, -12, -5, -22, -15, -4, -7] 
print "Maximum contiguous sum is", maxSubArraySum(a,len(a)) 
   
#This code is contributed by _Devesh Agrawal_ 

Above program can be optimized further, if we compare max_so_far with max_ending_here only if max_ending_here is greater than 0.

def maxSubArraySum(a,size): 
      
    max_so_far = 0
    max_ending_here = 0
      
    for i in range(0, size): 
        max_ending_here = max_ending_here + a[i] 
        if max_ending_here < 0: 
            max_ending_here = 0
          
        # Do not compare for all elements. Compare only    
        # when  max_ending_here > 0 
        elif (max_so_far < max_ending_here): 
            max_so_far = max_ending_here 
              
    return max_so_far 

Algorithm 4:  My algorithm

This is another solution proposed by: Pedram Agand

This method map the array to a corresponding 2*2*(n/2) table storing all local information. This algorithms employ divide and conquer method, so in each step, the 3rd element of table gets half. The total storage required is 4*log(n). Each elements are shown in this figure.

These are the definition of each element:

• Maximum Left Half (MLH): maximum between previous obtained value or by adding the new right piece.
• Maximum Right Half (MRH): maximum between previous obtained value or by adding the new left piece.
• Local Maximum (LM): maximum between previous two local maximum
• Sub sum (SS): the summation of all piece together

• MLH(new) = max (MLH(old,left) , SS(old,left)+MLH(old, right))
• MRH(new) = max (MRH(old, right) , SS(old, right)+MRH(old, left))
• LM(new) = max (LM(old, right) , LM(old, left))
• SS(new) = SS(old, right) + SS(old, left)

#!/usr/bin/python3
# This code is written by Pedram Agand (pagand@sfu.ca)
import numpy as np

def max_subarray(in_list, LEN):
    # Base case
    if (LEN == 1):
        if (np.asarray(in_list)>0):
            return in_list*np.ones(4)
        else:
            return np.array([0, 0, 0, np.asarray(in_list)])

    mid = int(LEN/2)
    DB1 = max_subarray(in_list[0:mid], mid)
    DB2 = max_subarray(in_list[mid:], LEN-mid)
    DB = np.zeros(4)
    DB[0] = np.amax([DB1[0], DB1[3]+DB2[0]])
    DB[1] = np.amax([DB1[1], DB2[1]])
    DB[2] = np.amax([DB2[2], DB1[2] + DB2[3]])
    DB[3] = DB1[3] + DB2[3]
    return DB

def main():
    in_list = [float(x) for x in raw_input("Enter numbers (separated by space):").split()]
    LEN = len(in_list)
    MaxSumArray = max_subarray(in_list, LEN)
    print("max sub array is:", np.max(MaxSumArray))

if __name__=='__main__':
    main()