如何在给定数组的每个i和i k(某个常数)之间找到所有最大值

Question

我需要在每个可能集的元素之间找到所有最大值{a [i]，a [i 1]，... a [i k]}（其中i是索引，k是一些常数）。为此，我正在使用。

loop(b, 1, k) {
       rloopl(i, b, n) {
           if(a[i] < a[i-1])
               a[i] = a[i-1];
       }
}

，但对于大阵列而言太慢了。还有其他更有效的方法吗？

Answer 1

我很抱歉告诉你，有了要求，答案是："否。"如果"最大的价值可以在任何地方"，那么您别无选择，只能"看 ...到处都是。"

对于任何特定的数据集，如果您"只做一次，一次只做一次"，那么您基本上只需要将肿块带走即可。您与" Brute-Force"一起卡住。

但是，如果您要做不止一次，和/或如果您对问题的数组获得的过程有一定的影响加载，情况可能会开始看起来更好。

例如，如果另一个代码添加了此数组的元素，则该代码会注意到它遇到的最大值/min值是微不足道的。加载二维数组的代码可能会收集有关每行（列）的统计信息。等等。这些策略"当时是免费的"，可以用来消除（或严重削减）以后进行特定的蛮力搜索。