如何找到在日志（n）的时间序列中任何范围的最大值？ [英] How to find maximum value in any range of an array in log(n) time?

问题描述

例如。阵列：{1,5，2，3，2，10}

E.g. Array: {1, 5, 2, 3, 2, 10}

范围：0-1答案：5 范围：2-4答案：3 范围：0-5答案：10 等等。

Range: 0-1 Answer: 5 Range: 2-4 Answer: 3 Range: 0-5 Answer: 10 etc.

推荐答案

如果阵列没有排序，那么有没有办法做到你的要求是什么。

If the array is not sorted, then there is no way to do what you're asking for.

要找到最大的，你至少需要的检查的范围内，这需要O的所有元素（ N 的）。

To find the maximum you at least need to inspect all elements in the range, which takes O(n).

如果您允许某种形式的数据preprocessing，这很容易。你可以只建立一个n ² 查找表的答案。然后，你可以找到最大的在固定时间内的任何范围。

If you allow some form of preprocessing of the data, it's easy. You could just build an n² lookup table with the answers. Then you could find the maximum for any range in constant time.

这篇关于如何找到在日志（n）的时间序列中任何范围的最大值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！