Input :
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
k = 3
SubArray : [1,2,3] , [2,3,1], [3,1,4] …..
Output :
3 3 4 5 5 5 6
Method 1)
– Keep Front pointer and endpointer to decide Window of subarray.
– For first SubArray find Max number and print.
– Keep Index of Max.
– increament pointers for Front & End. Check whether new element is larger than max or not.
– if larger mark it as max.
– if new SubArray crosses index of Max, Find new Max and Store index of it.
#include <stdio.h>
#include <iostream>
using namespace std;
void printKMax(int arr[], int n, int k)
{
int fr=0, max=arr[0],maxindex;
for(int i=0;i<k;i++){
if(arr[i]>=max) {max=arr[i]; maxindex=i;}
}
//cout<<“initialmax=”<<max<<” maxindex=”<<maxindex<<“n”;
cout<<max<<” “;
fr=1;
for (int i=k; i<n; i++)
{
if(maxindex>=fr && maxindex<=i){
if (arr[i] >= max){
max = arr[i];
maxindex=i;
}
}
else if(maxindex<fr){
max=arr[fr];
for(int j=fr;j<=i;j++){
if(arr[j]>=max){max=arr[j];maxindex=j;}
}
}
//cout<<“[“<<arr[fr]<<“-“<<arr[i]<<“] max=”<<max<<“n”;
cout<<max<<” “;
fr++;
}
}
int main()
{
//int arr[] = {12, 1, 78, 90, 57, 89, 56};
int arr[]={1,2,3,4,5,6,7,8,9,10,11};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
printKMax(arr, n, k);
return 0;
}
Working Code at : http://ideone.com/78MRE3