如何找到給定數組的每個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

我很抱歉地告訴你，在提出要求的情況下，答案是：「不」。如果「最大的價值可能在任何地方」，你別無選擇，只能到「看看 ......無處不在。」

如果你「一次只做一次」，對於任何特定的數據集，「那麼你基本上只需要把你的硬塊。你是卡住與「蠻力」。

然而，如果你做一次，這更和/或如果你對過程有一定的影響力，通過該有問題的數組被加載，情況可能開始尋找更好一點。例如，如果另一段代碼是一次一個地向該數組添加元素，那麼這段代碼就會注意到它遇到的最大/最小值，這是微不足道的。加載二維數組的代碼可能會收集有關每行（列）的統計信息。等等。這種「當時免費」的策略可以用來消除（或者嚴重削減）稍後進行特定強力搜索的需求。