SPOJ ARRAYSUB Solution

| July 01, 2015

The correct, optimal and working solution for programming question ARRAYSUB on spoj

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <deque>

void printKMax(int * arr, int n, int k)
{
    std::deque<int>  Qi(k);
 
    int i;
    for (i = 0; i < k; ++i)
    {
        while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
        	Qi.pop_back();  // Remove from rear
 
        Qi.push_back(i);
    }
 
    for ( ; i < n; ++i)
    {
        printf("%d " , arr[Qi.front()]);
 
        while ( (!Qi.empty()) && Qi.front() <= i - k)
            Qi.pop_front();  // Remove from front of queue
 
        while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
            Qi.pop_back();
 
        Qi.push_back(i);
    }
 
    printf("%d " , arr[Qi.front()]);
}

int main ( int argc , char * argv[] ) {

	int n , k;
	int * array;

	scanf("%d" , &n);

	array = ( int * ) malloc ( n * sizeof(int) );

	int i , j;
	for ( i = 0 ; i < n ; i++ ) {
		scanf("%d" , &array[i]);
	}

	scanf("%d" , &k);

	/*int max = array[0];
	int max_i = 0;
	for ( j = 0 ; j < k ; j++ ) {
		if ( array[j] > max ) {
			max = array[j];
			max_i = j;
		}
	}

	printf("%d " , max );

	for ( i = k ; i < n ; i++ ) {
		if ( array[i] > max ) {
			// New element greater than max
			max_i = i;
			max = array[i];
		}
		else if ( max_i == i-1 ) {
			// Recalculate max
			int max = array[i];
			for ( j = 0 ; j < k ; j++ ) {
				if ( array[j+1] > max ) {
					max = array[i+j];
					max_i = i+j;
				}
			}
		}
		else {
			// max will remain same
		}
		printf("%d " , max );
	}
	*/

	printKMax(array, n, k);

	printf("\n");
	return 0;
}