Как найти все максимальное значение между каждым 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

Мне очень жаль сообщить вам, что с требованием, представленным, ответ будет следующим: «нет». Если «наибольшее значение может быть где угодно», у вас нет выбора, кроме «Посмотрите ... везде».

Если вы делаете это «один раз и только один раз» для любого конкретного набора данных, тогда вам в основном просто нужно взять свои комки. Вы застряли с «грубой силой».

Однако если вы делаете это более , чем один раз, и/или если у вас есть какое-то влияние на процесс, с помощью которого массив в вопросе получает загружен, ситуация может начать смотреть немного лучше ,

Например, если другой фрагмент кода добавляет элементы к этому массиву один раз в один момент, для этого фрагмента кода тривиально заметить значение max/min, с которым он сталкивается. Код, загружающий двумерный массив, может собирать статистические данные о каждой строке (столбце). И так далее. Такие стратегии, которые являются «бесплатными в то время», могут быть использованы для устранения (или, строго говоря, сокращения) необходимости выполнения конкретных поисков грубой силы позже.