python - Maximum Subarray sum - Where is my solution wrong? Kadane's Algorithm

Question

Here is a description of the problem:

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:

max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) should be 6: [4, -1, 2, 1]

Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

My solution so far is:

def max_sequence(arr):
sum = 0
max = 0
for i in arr:
    sum += i


    if i > max:
        max = i
        sum = max
        

    elif sum > max:
        max = sum
    
return(max)

It works on simple examples but not on random ones... Could you please help me where I made a mistake / what I didn't consider?

Answer 1

this may be an alternative approach of doing it:

def consequtive_sub_lists(l): 
    sublists = []
    for iter, item in enumerate(l):
        sublists.append([item])
        cur_sublist = [item]
        for idx in range(iter+1, len(l)):
            cur_sublist.append(l[idx])
            sublists.append(cur_sublist.copy())
    return sublists
        
            
sublists = consequtive_sub_lists([1,2,-3,4])
max_sum, max_list = max([(sum(item), item) for item in sublists])
print(f"max_sum: {max_sum}")
print(f"max_list: {max_list}")

output:

max_sum: 4
max_list: [4]

Some Explanations: I sepparated the solution into 2 main steps:

• create all consequtive sub_lists out of given list (as list of lists)
• out of it, find out the element that has the maximum sum over it's elements

For the Kadane's algorithm (to make it similar to the solution in here)

def max_sequence(arr):
    max = 0
    sum = 0
    for i in arr:
        sum += i
        if sum > max:
            max = sum
        if sum < 0:
            sum = 0
        
    return max

this one is work