与えられた配列のすべての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

申し訳ありませんが、提示された要件では、答えは「いいえ」です。 「最大の価値がどこにでもあり得る」場合は、に「選択肢はありません。 ...どこでも見てください。」

特定のデータセットに対して「これを1回だけ実行する」のであれば、基本的にあなたの塊を取る必要があります。あなたはであり、は「brute-force」と貼り付けられています。

ただし、何度もこの多くをやっている場合は、および/またはあなたが問題の配列はがロードされる過程に何らかの影響、を持っている場合は、状況は少し良く探し始めるかもしれません。

たとえば、別のコードがこの配列に1つずつ要素を追加している場合、そのコードが検出した最大/最小値に気付くのは簡単です。 2次元配列をロードするコードは、各行（列）に関する統計を収集することがあります。等々。 「当時は無料だった」このような戦略は、後に特定のブルートフォース検索を行う必要性を排除する（またはひどく削減する）ために使用することができます。