def max_sum_subarray(arr):
cur_max_sum = global_max_sum = arr[0]
start = end = 0
sz = len(arr)
for i in range(1, sz):
cur_max_sum = max(arr[i], cur_max_sum+arr[i])
global_max_sum = max(global_max_sum, cur_max_sum)
if cur_max_sum > global_max_sum:
global_max_sum = cur_max_sum
end = i
g = global_max_sum
for i in range(end, -1, -1):
g -= arr[i]
if not g:
start = i
break
ans = {
'global_max_sum': global_max_sum,
'start': start+1,
'end': end+1
}
return ans
Here, start
and end
don't get updated inside for loop under if
, though the condition satisfies.
If start
or end
is used out of if
, there is no problem with it. Is there any scoping problem or something else? Please explain me in details.
Thanks in advance.
It's a logic error:
global_max_sum = max(global_max_sum, cur_max_sum)
if cur_max_sum > global_max_sum:
There's literally no way for cur_max_sum
to be greater than global_max_sum
.