如何获取最大和子数组的起始索引
how to get start index for maximum sum sub array
我正在使用以下程序查找 sum.I 的最大总和和索引,我能够获得正确的索引,但找不到正确的索引。
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))
我收到了
(5, 2)
这是预期的,但我也想获得起始索引,在这种情况下应该是 1
所以我期待
(5, 1, 2)
这里有什么方法可以得到起始索引吗?我应该如何将变量放入记录起始索引?
您只需应用与 r_index
相同的逻辑。每当您更改 max_current
时,最大子数组的 start 就会更改 。最后看起来像这样
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)
我正在使用以下程序查找 sum.I 的最大总和和索引,我能够获得正确的索引,但找不到正确的索引。
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))
我收到了
(5, 2)
这是预期的,但我也想获得起始索引,在这种情况下应该是 1
所以我期待
(5, 1, 2)
这里有什么方法可以得到起始索引吗?我应该如何将变量放入记录起始索引?
您只需应用与 r_index
相同的逻辑。每当您更改 max_current
时,最大子数组的 start 就会更改 。最后看起来像这样
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)