Max Sum Contiguous Subarray

Question

This is a maximum sum contiguous problem from interviewbit.com

Problem : Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example: Given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

This is my solution :

def max_sub_array(array):
 """ Finds msub-array with maximum sum and returns the maximum sum and sub-array"""
 max_start, max_stop = 0, 1 # Start, Stop of maximum sub-array
 curr = 0 # pointer to current array
 max_sum = array[0] # Sum of maximum array
 current_sum = 0 # sum of current array
 for i, elem in enumerate(array):
 current_sum += elem
 
 if max_sum < current_sum:
 max_sum = current_sum 
 max_start = curr
 max_stop = i + 1
 if current_sum < 0:
 current_sum = 0
 curr = i + 1
 
 return max_sum , array[max_start:max_stop]

checking test cases:

assert max_sub_array([-4,-2,-3,-4,-5]) == (-2,[-2]), "Wrong evaluation"
assert max_sub_array([-1]) == (-1,[-1]), "Wrong evaluation"
assert max_sub_array([-5, 1, -3, 7, -1, 2, 1, -4, 6]) == (11,[7, -1, 2, 1, -4, 6]), "Wrong evaluation"
assert max_sub_array([-5, 1, -3, 7, -1, 2, 1, -6, 5]) == (9, [7, -1, 2, 1]), "Wrong evaluation"
assert max_sub_array( [6, -3, -2, 7, -5, 2, 1, -7, 6]) == (8,[6, -3, -2, 7]), "Wrong evaluation"
assert max_sub_array([-5, -2, -1, -4, -7]) == (-1,[-1]), "Wrong evaluation"
assert max_sub_array( [4, 1, 1, 4, -4, 10, -4, 10, 3, -3, -9, -8, 2, -6, -6, -5, -1, -7, 7, 8]) == (25,[4, 1, 1, 4, -4, 10, -4, 10, 3]), "Wrong evaluation"
assert max_sub_array([4, -5, -1, 0, -2, 20, -4, -3, -2, 8, -1, 10, -1, -1 ]) == (28, [20, -4, -3, -2, 8, -1, 10]), "Wrong evaluation"

How can this code be optimised ?

• esote: It is a known problem in computer science as @kaushal says. Kadane's algorithm is \$O(n)\$ (linear run time complexity) and is probably as good as it gets.

Answer 1

Expanding upon my comment:

Here is Kadane's algorithm:

def max_subarray(arr):
 max_ending = max_current = arr[0]
 for i in arr[1:]:
 max_ending = max(i, max_ending + i)
 max_current = max(max_current, max_ending)
 return max_current
print(max_subarray([-4, -2, -3, -4, 5])) # 5
print(max_subarray([4, -5, -1, 0, -2, 20, -4, -3, -2, 8, -1, 10, -1, -1])) # 28

Like your algorithm, it is \$O(n)\$. However, it does fewer operations while looping. You could then alter it to return the array which gives that sum, which shouldn't be too hard.

Answer 2

You have written to start a new subarray,

 if current_sum < 0:
 current_sum = 0
 curr = i + 

It is not necessary that current_sum < 0 to start a new subarray. We should be creating a new subarray only when it is less than the current element, i.e. current_sum < array[i].

I have implemented this in C++:

void maximum_sum_subarray(int n, int arr[])
{
 // variables for global maximum_sum_subarray
 int maxSoFar = arr[0], maxSoFarLeft = 0, maxSoFarRight = 0;
 // variables for current subarray
 int thisSubarraySum = arr[0], thsSubarrayleft = 0, thisSubarrayRight = 0;
 for (int i = 1; i < n; i++)
 {
 int sumInThisSubArray = arr[i] + thisSubarraySum;
 // if sum is less then current elements
 // means that we can start a new suarray
 if (arr[i] > sumInThisSubArray)
 {
 thisSubarraySum = arr[i];
 thsSubarrayleft = i;
 thisSubarrayRight = i;
 // if this subarray has sum than 
 // previous largest subarray
 // then reassign max_subarray diamensions
 if (maxSoFar < thisSubarraySum)
 {
 maxSoFar = thisSubarraySum;
 maxSoFarLeft = thsSubarrayleft;
 maxSoFarRight = thisSubarrayRight;
 }
 }
 // else continue this subarray
 else
 {
 thisSubarraySum = sumInThisSubArray;
 thisSubarrayRight = i;
 }
 }
 cout << maxSoFarLeft << " " << maxSoFarRight << " " << maxSoFar << endl;
}

You can refer to this link: https://www.youtube.com/watch?v=2MmGzdiKR9Y

Answer 3

It goes without saying that this is a well known problem. ref

Your code is already linear in the input, takes a single pass over the array, and does the minimum possible checks (if statements) and update assignments for the involved variables.

It cannot be optimised any further.

• Dan Oberlam: Welcome to Code Review! Whilst this may theoretically answer the question, it would be preferable to include the essential parts of the answer here, and provide the link for reference.