1
\$\begingroup\$

The following code is my solution for the following Daily Coding Challenge

Given an array of numbers, find the maximum sum of any contiguous subarray of the array.

For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.

Given the array [-5, -1, -8, -9], the maximum sum would be 0, since we would not take any elements.

Do this in O(N) time.

I think this is done in O(N) time and is the best solution. If someone can think of a better way, I would be interested.

array = [4, -2, 7, -9]
running_sum = 0
for i in range(1,len(array)):
    if array[i-1] > 0:
        array[i] = array[i] + array[i-1]
    else: 
        array[i-1] = 0
print(max(array))
\$\endgroup\$
  • 2
    \$\begingroup\$ You can remove running_sum = 0 :) \$\endgroup\$ – dfhwze Jun 22 at 18:22
  • 1
    \$\begingroup\$ Although it is not specified in the problem statement, the space complexity is also important. Your algorithm exhibits an \$O(n)\$ time complexity (because it mutates an array). There exists a constant space, linear time solution. \$\endgroup\$ – vnp Jun 22 at 19:05
  • \$\begingroup\$ Surely you have to store the array to process it. Therefore my not making a new variable, the space complexity is the same? @vnp \$\endgroup\$ – EML Jun 22 at 21:28
  • 1
    \$\begingroup\$ The space complexity does not account for the space taken by the input. \$\endgroup\$ – vnp Jun 22 at 21:29
  • \$\begingroup\$ I am curious how this would work. Because saying something like max_value = maximum(max_value, max_value + array[i]) wouldn't work. How can you predict the i+1 or i+2 value in linear time complexity. Any clues? Thanks \$\endgroup\$ – EML Jun 22 at 21:33
1
\$\begingroup\$

changing mutable object

Since you are changing the original array, this code run twice can provide strange results. In general I try to avoid changing the arguments passed into a function I write, unless it's explicitly stated, or expected (like list.sort)

accumulate

What you are looking for is the largest difference between tha cumulative sum where the minimum comes before the maximum. Calculating the cumulative sum can be done with itertools.accumulate. Then you just have to keep track of the minimum of this running sum and the difference with the running minimum

def best_sum_accum(array):
    running_min = 0
    max_difference = 0
    for cumsum in accumulate(array):
        if cumsum > running_min:
            max_difference = max(max_difference,  cumsum - running_min)
        running_min = min(running_min, cumsum)
    return max_difference
\$\endgroup\$
  • \$\begingroup\$ Surely this has a time complexity > O(N) because you have a nested loop? for and max? \$\endgroup\$ – EML Jun 23 at 10:47
  • 1
    \$\begingroup\$ Not really, you loop 1 timer through the array. On each iteration, you compare 2 numbers, so the time complexity is linear with the length of the array. Space complexity is constant \$\endgroup\$ – Maarten Fabré Jun 23 at 12:52
1
\$\begingroup\$

I would merge the 2 loops (there is one in the max part), since not all parts are relevant for the maximum:

def best_subsum(array):
    running_sum = 0
    for i in range(1,len(array)):
        if array[i-1] > 0:
            array[i] = array[i] + array[i-1]
            if array[i] > running_sum: running_sum = array[i]
    return running_sum

array = [4, -2, 7, -9]
print(best_subsum(array))

Note that branch prediction shouldnt be too much of a problem, since running sum is not check until the same if statement in the next succeding iteration.

\$\endgroup\$

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.