Как установить цепочный код на другом канале

Вы слышали об этом в O (n) с использованием dequeue.

Хорошо, что это хорошо известный алгоритм для этого вопроса в O (n).

Метод, который я рассказываю, достаточно прост и требует динамического программирования и имеет временную сложность O ( n).

Your Sample Input:
n=10 , W = 3

10 3
1 -2 5 6 0 9 8 -1 2 0

Answer = 5 6 6 9 9 9 8 2

Концепция: Динамическое программирование

Алгоритм:

1. N - количество элементов в массиве, а W - размер окна. Итак, номер окна = N-W + 1
2. Теперь разделим массив на блоки из W, начиная с индекса 1. Здесь разделите на блоки размера «W» = 3. Для ввода образца: [/g1]
3. Мы разделили на блоки, потому что мы рассчитаем максимум двумя способами A.), пройдя слева направо B.), пройдя справа налево , но как?
4. Во-первых, перемещение слева направо. Для каждого элемента ai в блоке мы найдем максимум до тех пор, пока этот элемент ai не начнет от START блока до END этого блока. Итак, здесь [/g2]
5. Во-вторых, перемещение справа налево. Для каждого элемента 'ai' в блоке мы найдем максимум до тех пор, пока этот элемент 'ai' не станет от END блока до START этого блока. Итак, [/g3]
6. Теперь нам нужно найти максимум для каждого подмассива или окна размера «W». Итак, начиная с индекса = 1 до индекса = N-W + 1. max_val[index] = max(RL[index], LR[index+w-1]); [/g4]

    for index=1: max_val[1] = max(RL[1],LR[3]) = max(5,5)= 5
   

Симметрично, для всех индексов i, (i<=(n-k+1)) значение в RL[i] и LR[i+w-1] равно сравнительный и максимальный среди этих двух ответов для этого подмассива.

Итак, окончательный ответ: 5 6 6 9 9 9 8 2

Сложность времени: O (n)

Код реализации:

// Shashank Jain
#include 
#include 
#include 
#include 

#define LIM 100001 

using namespace std;

int arr[LIM]; // Input Array
int LR[LIM]; // maximum from Left to Right
int RL[LIM]; // maximum from Right to left
int max_val[LIM]; // number of subarrays(windows) will be n-k+1

int main(){
    int n, w, i, k; // 'n' is number of elements in array
                    // 'w' is Window's Size 
    cin >> n >> w;

    k = n - w + 1; // 'K' is number of Windows

    for(i = 1; i <= n; i++)
        cin >> arr[i];

    for(i = 1; i <= n; i++){ // for maximum Left to Right
        if(i % w == 1) // that means START of a block
            LR[i] = arr[i];
        else
            LR[i] = max(LR[i - 1], arr[i]);        
    }

    for(i = n; i >= 1; i--){ // for maximum Right to Left
        if(i == n) // Maybe the last block is not of size 'W'. 
            RL[i] = arr[i]; 
        else if(i % w == 0) // that means END of a block
            RL[i] = arr[i];
        else
            RL[i] = max(RL[i+1], arr[i]);
    }

    for(i = 1; i <= k; i++)    // maximum
        max_val[i] = max(RL[i], LR[i + w - 1]);

    for(i = 1; i <= k ; i++)
        cout << max_val[i] << " ";

    cout << endl;

    return 0;
}  

Запуск кода Link

---

Я попытаюсь доказать: (by @ johnchen902 )

Если k % w != 1 (k не является началом блока)

Let k* = The begin of block containing k
ans[k] = max( arr[k], arr[k + 1], arr[k + 2], ..., arr[k + w - 1])
       = max( max( arr[k],  arr[k + 1],  arr[k + 2],  ..., arr[k*]), 
              max( arr[k*], arr[k* + 1], arr[k* + 2], ..., arr[k + w - 1]) )
       = max( RL[k], LR[k+w-1] )

В противном случае (k - начало блока)

ans[k] = max( arr[k], arr[k + 1], arr[k + 2], ..., arr[k + w - 1])
       = RL[k] = LR[k+w-1]
       = max( RL[k], LR[k+w-1] )