Maximum of all sub-arrays of size k
PROBLEM :
Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.
Input:
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer 'N' denoting the size of array and the size of subarray 'k'.
The second line contains 'N' space-separated integers A1, A2, ..., AN denoting the elements of the array.
Output:
Print the maximum for every subarray of size k.
Constraints:
1 = T = 200
1 = N = 100
1 = k = N
0 =A[i]<1000
Example:
Input:
2
9 3
1 2 3 1 4 5 2 3 6
10 4
8 5 10 7 9 4 15 12 90 13
Output:
3 3 4 5 5 5 6
10 10 10 15 15 90 90
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t ;
cin>>t ;
while(t--)
{
int no,k ;
cin>>no>>k ;
int arr[no] ;
for(int i=0;i<no;i++)
cin>>arr[i] ;
deque<int> dque(k) ;
for(int i=0;i<k;i++)
{
while(!dque.empty() && arr[i]>=arr[dque.back()])
dque.pop_back() ;
dque.push_back(i) ;
}
for(int i=k;i<no;i++)
{
cout<<arr[dque.front()]<<" " ;
while(!dque.empty() && dque.front()<=i-k)
dque.pop_front() ;
while(!dque.empty() && arr[i]>=arr[dque.back()])
dque.pop_back() ;
dque.push_back(i) ;
}
cout<<arr[dque.front()]<<" " ;
cout<<endl ;
}
return 0;
}
---------------------------------------------------------------------------------
Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.
Input:
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer 'N' denoting the size of array and the size of subarray 'k'.
The second line contains 'N' space-separated integers A1, A2, ..., AN denoting the elements of the array.
Output:
Print the maximum for every subarray of size k.
Constraints:
1 = T = 200
1 = N = 100
1 = k = N
0 =A[i]<1000
Example:
Input:
2
9 3
1 2 3 1 4 5 2 3 6
10 4
8 5 10 7 9 4 15 12 90 13
Output:
3 3 4 5 5 5 6
10 10 10 15 15 90 90
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t ;
cin>>t ;
while(t--)
{
int no,k ;
cin>>no>>k ;
int arr[no] ;
for(int i=0;i<no;i++)
cin>>arr[i] ;
deque<int> dque(k) ;
for(int i=0;i<k;i++)
{
while(!dque.empty() && arr[i]>=arr[dque.back()])
dque.pop_back() ;
dque.push_back(i) ;
}
for(int i=k;i<no;i++)
{
cout<<arr[dque.front()]<<" " ;
while(!dque.empty() && dque.front()<=i-k)
dque.pop_front() ;
while(!dque.empty() && arr[i]>=arr[dque.back()])
dque.pop_back() ;
dque.push_back(i) ;
}
cout<<arr[dque.front()]<<" " ;
cout<<endl ;
}
return 0;
}
---------------------------------------------------------------------------------
Comments
Post a Comment