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

Question

我有一些每秒记录的数据并测量一些值，我可以绘制它的图形并查看分布情况，但是如何找到具有最大总和或间隔的子数组如果所有值为正，则最大值？

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

Answer 1

如果数组包含负数，您可以只使用Kadane's Algorithm。但是由于你的数组都是正整数，你可以自己解决。

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

使用此解决方案，您一天可以有多个 "hottest parts"。这是有道理的，因为如果它在一天中的两个不同时间爬升到相同的温度怎么办？

如果你只想要一个子数组作为结果，那么在计算完上面的结果后，你可以选择和最大的子数组（将子数组中的所有值相加）。

要对数组进行归一化，首先要计算数组的均值。然后从数组中的每个值中减去平均值。现在数组以零为中心。然后找到数组中的最大值。将数组中的每个值除以最大值。现在数组中的最大值是一个。无论数组的最大值或平均值如何，归一化都可以让您准确地对数据进行阈值处理。

这是 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

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

How to find maximum interval in a graph?

python

arrays

math

graph