I need to create a maxSequence() function ,that has a user input for a list and it takes the input list as an argument and it returns a sublist whose values sequence gibve us the maximum sum in the list .
So if we call the maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]). It should return : 6: [4, -1, 2, 1]
You have to brute force it.
Edit: There are faster algorithms than my brute force solution. (thanks @user2357112
)
Construct all sublists and check which has the biggest sum. To construct all sublists start at start=0 and end=start+1, then increase end until the result is the whole list, repeat that step with an increased start etc:
a = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max = sum(a)
l = a[:]
for start in range(len(a)):
for end in range(start, len(a)):
s = sum(a[start:end+1])
if s > max:
max = s
l = a[start:end+1]
print(max, l)
Result:
6 [4, -1, 2, 1]
The lists you check are (in that order):
[-2]
[-2, 1]
[-2, 1, -3]
[-2, 1, -3, 4]
[-2, 1, -3, 4, -1]
[-2, 1, -3, 4, -1, 2]
[-2, 1, -3, 4, -1, 2, 1]
[-2, 1, -3, 4, -1, 2, 1, -5]
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
[1]
[1, -3]
[1, -3, 4]
[1, -3, 4, -1]
[1, -3, 4, -1, 2]
[1, -3, 4, -1, 2, 1]
[1, -3, 4, -1, 2, 1, -5]
[1, -3, 4, -1, 2, 1, -5, 4]
[-3]
[-3, 4]
[-3, 4, -1]
[-3, 4, -1, 2]
[-3, 4, -1, 2, 1]
[-3, 4, -1, 2, 1, -5]
[-3, 4, -1, 2, 1, -5, 4]
[4]
[4, -1]
[4, -1, 2]
[4, -1, 2, 1]
[4, -1, 2, 1, -5]
[4, -1, 2, 1, -5, 4]
[-1]
[-1, 2]
[-1, 2, 1]
[-1, 2, 1, -5]
[-1, 2, 1, -5, 4]
[2]
[2, 1]
[2, 1, -5]
[2, 1, -5, 4]
[1]
[1, -5]
[1, -5, 4]
[-5]
[-5, 4]
[4]
