Editorial for ARRAYSUB - subarrays -- SPOJ - UCS - Unleash-Coding-Skills

Monday, 5 March 2018

Editorial for ARRAYSUB - subarrays -- SPOJ - UCS





This is editorial for the problem in link:

 http://www.spoj.com/problems/ARRAYSUB/

Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.

Input

the number n denoting number of elements in the array then after a new line we have the numbers of the array and then k in a new line
n < 10^6
k < 10^5
1 <= k <= n
and each element of the array is between 0 and 10^6
(Edited: In fact, n <= 10^5)

Output

print the output array

Example

Input:
9
1 2 3 1 4 5 2 3 6
3

Output:
3 3 4 5 5 5 6
 
For this problem a brute Force solution is enough.

     #include <iostream>

    using namespace std;

     

    int main() {

        long int i,j,k,n,a[100002],maxi;

        cin>>n;

//Take Input of array

        for(i=1;i<=n;i++)

        cin>>a[i];

        cin>>k;

//For every element in array up to n-k+1 terms see all next k element max and

//print the value in the given set

        for(i=1;i<=n-k+1;i++)

        {

            maxi=a[i];

            for(j=i;j<i+k;j++)

            {

                if(maxi<a[j])

                maxi=a[j];

            }
//printing output for the code
            cout<<maxi<<" ";

        }

        return 0;
} 
 

   

 Happy Coding........

Share your views in comment section below   ........

No comments:

Post a comment