7
\$\begingroup\$

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 ?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – esote
    Jul 10 '18 at 2:27
5
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ May 10 '18 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.