Why does my 'Maximum Contiguous Subarray Sum' solution not work for all inputs?

Question

For context, this is the problem statement in Codewars: Problem Statement

It's essentially the classic 'Find the maximum subarray sum' problem, though with the important added detail of the fact that a '0' should be returned given an array of all negative numbers, instead of just the largest negative number value.

To begin with, I'm fully aware that this solution is not a terribly good or efficient one. That being said, the logic to me still makes sense so I don't quite understand why it works for certain inputs and not others. I can't provide the inputs for which this program is invalid due to the fact that the test cases are hidden in Codewars.

I've tried running the code using examples like;

[1, 0, 2, -3, 6] (should return 6)
[-2, 1, -3, 4, -1, 2, 1, -5, 4] (should return 6)
[-2, -3, 4, -1, 5, 1, 5, -3] (should return 14)
etc. And they've all worked fine

Again, I just wanna know the logic behind why this code is incorrect. I'm not looking for an alternative solution that is correct (I'm already aware of the existence of Kadane's algorithm now). This was my first blind attempt at solving this problem so I'd really like to know what I did wrong so that I can learn from it.

def max_sequence(arr):
    max_sum = 0
    max_subarr_index = 0
    for i, val in enumerate(arr):
        max_sum = max(max_sum, sum(arr[max_subarr_index:i+1]), val)
        if max_sum == val:
            max_subarr_index = i
    return max_sum

user4668606 · Accepted Answer · 2021-05-04 16:36:59Z

1

The flaw lies in the fact that max_sum has a dual usage in your algorithm. It's used to:

keep the maximum found sum over the so far explored array
update max_subarr_index if the larger array starts directly at index i instead of max_subarr_index

For the first point, your algorithm works just fine. For the second it fails, because max_sum needn't have anything to do with the subarray you're currently looking at. E.g.:

arr = [3, -4, 1, 1, ...]

Now for i = 3 the variables look like this:

max_sum = 3
max_subarr_index = 0

I.e. the algorithm still "thinks" the maximum subarray starts at index 0 and has the sum 3. However the maximum subarray ending at index 3 is actually [1, 1] with max_subarr_index = 2. I.e. there's actually two maximum subarrays:

the global one ([3] for i = 3)
the maximum sum subarray ending at the current index ([1, 1] for i = 3)

You can fix this by updating max_subarr_index based only on the maximum of val and sum(arr[max_subarr_index:i+1]):

def max_sequence(arr):
    max_sum = 0
    max_subarr_index = 0
    for i, val in enumerate(arr):
        # update max_subarr_index based on sum of "current" max subarray
        tmp = max(sum(arr[max_subarr_index:i+1]), val)
        if tmp == val:
            max_subarr_index = i

        # global maximum found so far
        max_sum = max(max_sum, tmp)
        
    return max_sum

answered May 4, 2021 at 16:36

user4668606

Sign up to request clarification or add additional context in comments.

1 Comment

dettolas Over a year ago

Ahh ok i see my flaw in logic now, thank you for the thorough response!

Collectives™ on Stack Overflow

Why does my 'Maximum Contiguous Subarray Sum' solution not work for all inputs?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related