Algorithm to find best 8 minute window in a 1 hour run

Question

An activity runs for a bit more than an hour. I need to get the best 8 minute window, where some parameters are maximum.

For example, a value x is measured every second. If my activity runs for one hour, I get 3600 values for x. I need to find the best continuous 8 minute time interval where the x value was the highest among all the others.

If I capture, say, from 0th minute to 8th minute, there may be another time frame like 0.4 to 8.4 where it was maximum. The granularity is one second. We need to consider every second.

Please help me with the design.

Answer 1

What is preventing you from just trying every possibility? 3600 values is not many. You can run through them in O(n*m) time where n in the number of data points and m in the number of points in the window.

If you want to make an optimization you can do it in O(n) by using a sliding window. Keep a queue of all the values of x within the first 8 minutes, and the total for that 8 minutes. Every time you advance one second you can dequeue the oldest value of x and subtract it from your running total. Then add the new value of x to the queue and add it to the total.

But this optimization hardly seems necessary for the size of problem you have. I'd recommend keeping it simple unless the extra performance is necessary.

Answer 2

Something along the lines of this:

int[] xs = { 1, 9, 5, 6, 14, 9, 6, 1, 5, 4, 7, 16, 8, 3, 2 };

int bestEndPos = 0;
int bestSum = 0;

int currentSum = 0;
for (int i = 0; i < xs.length; i++) {

    // Add the current number to the sum.
    currentSum += xs[i];

    // Subtract the number falling out behind us.
    if (i >= 8)
        currentSum -= xs[i - 8];

    // Record our new "best-last-index" if we beat our previous record!
    if (currentSum > bestSum) {
        bestEndPos = i;
        bestSum = currentSum;
    }
}

System.out.println("Best interval: " + (bestEndPos - 8 + 1) + "-" + bestEndPos);
System.out.println("Has interval-sum of: " + bestSum);