CODEWITHSUNDEEP
pythonarraysmathgraph
Toshiro
Toshiro

Reputation: 345

How to find maximum interval in a graph?

I have some data that is recorded every second and measures some value, I can draw a graph of it and see how the distribution looks, but how do I find the the sub array with the maximum sum or the interval with the greatest values if all values are positive?

If the graph was measuring temperature for example how would I find out what interval of the day was the hottest from a time v.s. temp graph?(both of which are arrays in my program)

Upvotes: 0

Views: 471

Answers (1)

five_dollar_shake
five_dollar_shake

Reputation: 378

If the array contained negative numbers, you could just use Kadane's Algorithm. But since your array is all positive integers, you can make your own solution.

One way is to normalize the array and then threshold the values. Then iterate through the array, and when you see a value go above the threshold, save that index in the array as the beginning of the sub array. When the value goes back below the threshold, save that index as the end of the sub array.

With this solution, you can have multiple "hottest parts" of the day. This makes sense, because what if it climbs to the same temperature at two different parts of the day?

If you want only one sub array as a result, then after you compute the above result, you can pick the sub array with the greatest sum (summing all the values in the sub array).

To normalize the array, first calculate the mean of the array. Then subtract the mean from each value in the array. Now the array is centered around zero. Then find the maximum value in the array. Divide each value in the array by the maximum value. Now maximum value in the array is one. Normalizing allows you to threshold the data accurately regardless of the maximum value or average value of the array.

Here's the python code (x is the input array as a numpy array ):

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

Upvotes: 1

Related Questions