如何在图中找到最大间隔？

Question

我有一些每秒记录的数据，测量一些值，我可以画一张图，看看分布如何，但是如果所有值都是正的，我如何找到最大和的子数组或最大值的区间？在

例如，如果图表是测量温度的，我如何从时间v.s.温度图中找出一天中哪个时段最热？（这两个都是我程序中的数组）

Answer 1

如果数组包含负数，可以使用Kadane's Algorithm。但由于数组都是正整数，所以您可以自己制定解决方案。在

一种方法是规范化数组，然后对值设置阈值。然后遍历数组，当看到某个值超过阈值时，将该索引保存在数组中作为子数组的开头。当值回到阈值以下时，将该索引保存为子数组的末尾。在

有了这个解决方案，你可以有多个“最热的部分”一天。这是有道理的，因为如果它在一天中的两个不同的时间上升到相同的温度呢？在

如果只希望得到一个子数组，那么在计算上述结果之后，可以选择求和最大的子数组（将子数组中的所有值相加）。在

要规范化数组，首先计算数组的平均值。然后从数组中的每个值减去平均值。现在数组以零为中心。然后在数组中找到最大值。将数组中的每个值除以最大值。现在数组中的最大值是1。规范化允许您准确地为数据设置阈值，而不管数组的最大值或平均值是多少。在

下面是python代码（x是作为numpy数组的输入数组）：

def getMaxSubArrays(x):
    y=x-np.mean(x)
    z=y/y.max()
    maxSubArrays=[]
    subFound=False
    begin=0
    for i in range(len(z)):
        if z[i]>0.75 and subFound==False:
            subFound=True
            begin=i
        elif z[i]<=0.75 and subFound==True:
            subFound=False
            maxSubArrays.append((begin,i))
    for subarray in maxSubArrays:
        print "subarray found: index ",subarray[0]," to ",subarray[1], x[subarray[0]:subarray[1]]
    return maxSubArrays