Created
March 22, 2014 19:24
-
-
Save iRajul/9712829 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
The method i am telling is quite Simple and requires Dynamic Programming and have time complexity 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 | |
Concept: Dynamic Programming | |
Algorithm: | |
N is number of elements in an array and W is window size . So, Window number = N-W+1 | |
Now divide array into block of W starting from index 1. | |
here divide into block of size 'W'=3. For your sample input: | |
divided blocks | |
Why we divided in block because we will calculate maximum in 2 ways A.) by traversing from left to right B.) by traversing from right to left. but how ?? | |
Firstly, Traversing from Left to Right. For each element ai in block we will find maximum till that element ai starting from START of Block to END of that block. so Here, | |
LR | |
Secondly, Traversing from Right to Left. For each element 'ai' in block we will find maximum till that element 'ai' starting from END of Block to START of that block. so Here, | |
RL | |
Now we have to do is find maximum for each subarray or window of size 'W'. so, starting from index = 1 to index = N-W+1 . | |
max_val[index] = max(RL[index], LR[index+w-1]); | |
LR + RL | |
for index=1: max_val[1] = max(RL[1],LR[3]) = max(5,5)= 5 | |
Simliarly, for all index i, (i<=(n-k+1)), value at RL[i] and LR[i+w-1] are compared and maximum among those two is answer for that subarray. | |
So Final Answer : 5 6 6 9 9 9 8 2 | |
Time Complexity: O(n) | |
Implementation code: | |
// Shashank Jain | |
#include <iostream> | |
#include <cstdio> | |
#include <cstring> | |
#include <algorithm> | |
#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]); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment