CODEWITHSUNDEEP
pythonalgorithm
dettolas
dettolas

Reputation: 13

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

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;

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

Upvotes: 1

Views: 420

Answers (1)

user4668606
user4668606

Reputation:

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

  1. keep the maximum found sum over the so far explored array

  2. 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

Upvotes: 1

Related Questions