Maximum subarray problem

For starters, let us look at an interesting problem. In this problem, the goal is to find the maximum contiguous subarray of an array (sequence) of integers having mixed negative and positive numbers.

For example, say we have the following array:

>>> a  = [-5, 20, -10, 30, 15]

It is pretty obvious with a quick scan that the maximum sum is for the subarray [20, -10, 30, 15], giving a sum of 55.

Let us say, as a first cut, you write this piece of code:

import itertools

# max_subarray: v1
def max_subarray(sequence):
    """ Find sub-sequence in sequence having maximum sum """
    
    sums = []
    
    for i in range(len(sequence)):
        # Create all sub-sequences in given size
        for sub_seq in itertools.combinations(sequence, i):
            # Append sum
            sums.append(sum(sub_seq))

    return max(sums)

Now let's try it out:

>>>  max_subarray([-5, 20, -10, 30, 15])
65

This output seems clearly wrong, as any manual addition of any subarray...