# Max Sum Contiguous Subarray

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 ?

• 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. Jul 10 '18 at 2:27

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.

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

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.

• 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. May 10 '18 at 22:49