查找总和最小的子数组的索引 [英] Find the index of the subarray whose sum is minimum
问题描述
给出一个长度为n的数组,该数组带有整数(可以是负数或正数).找到子数组的开始和结束索引,并尽可能减少总和.
Given an array of length n, with integers(can be negative or positive). Find the starting and ending index of the subarray with minimum sum possible.
推荐答案
正如您所指定的,这是关于Kadanes算法的,很容易找到很多有关它的参考. GeeksForGeeks:最小和连续子数组请对该算法进行解释并提供实现几种语言.
As you specified this is about Kadanes Algorithm, it is easy to find a lot of references about it. GeeksForGeeks : Smallest sum contiguous subarray kindly explains about the algorithm and provides implementations in a few languages.
基于 python 代码的问题,我对其进行了修改,以返回开始/结束索引而不是总和值.这个想法是保持范围索引和总和值.
Based on the python code from that page, I have revised it to return begin/end indices rather than the sum value. The idea is keeping the range indices along with the sum value.
import sys
def smallestSumSubarr(arr, n):
min_ending_here = sys.maxint
min_so_far = sys.maxint
min_so_far_range = (-1, 0) # save indices
for i in range(n):
if (min_ending_here > 0):
min_ending_here = arr[i]
min_ending_here_range = (i, i) # start over
else:
min_ending_here += arr[i]
min_ending_here_range = (min_so_far_range[0], i) # extend the range
if min_so_far > min_ending_here: # update both value and range
min_so_far = min_ending_here
min_so_far_range = min_ending_here_range
return min_so_far_range # return range instead of value
# Usage
arr = [3, -4, 2, -3, -1, 7, -5]
n = len(arr)
print "Smallest sum range(inclusive): ", smallestSumSubarr(arr, n)
在STDOUT上,您将看到
On STDOUT, you will see
Smallest sum range(inclusive): (1, 4)
这篇关于查找总和最小的子数组的索引的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!