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 += iif i > max:max = isum = maxelif sum > max:max = sumreturn(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?
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 sublistssublists = 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 = 0sum = 0for i in arr:sum += iif sum > max:max = sumif sum < 0:sum = 0return max
this one is work