I am using the following program to find the maximum sum and indices of the sum.I am able to get the right index but having trouble finding the right index.
def max_sum_new(a):
max_current = max_global = a[0]
r_index = 0
for i in range(1, len(a)):
max_current = max(a[i], max_current+a[i])
if max_current > max_global:
max_global = max_current
r_index = i
return (max_global, r_index)
#Driver Code:
my_arr = [-2, 3, 2, -1]
print(max_sum_new(my_arr))
I am getting
(5, 2)
which is expected but i also want to get the starting index which in this case should be 1
so i expect
(5, 1, 2)
is there any way to get a start index here? How should i put the variable to record start index?
You just need to apply the same logic as you did with r_index
. Whenever you change the max_current
, that's when the start of the maximum sub-array changes. In the end it looks like this
max_current = max_global = a[0]
r_index = 0
left_index = 0
for i in range(1, len(a)):
if a[i] > max_current + a[i]:
# Here is where your start index changes
left_index = i
max_current = a[i]
else:
max_current = a[i] + max_current
if max_current > max_global:
max_global = max_current
r_index = i
print(max_global, left_index, r_index)