5
\$\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
    \$\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
2
\$\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\$
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\$
  • 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\$ – Dannnno 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.