C ++: find the maximum integer in an array of submatrices

Question

I ran into a problem when I want to write an algorithm that can return the maximum element of each consecutive submatrix of k elements in a larger array, and these maximum elements are read into their own array, for example:

Given int array = {3, 7, 20, 6, 12, 2, 0, 99, 5, 16}, and int k = 4,
--> creates the array {20, 20, 20, 12, 99, 99, 99} 
[because there are 7 consecutive sub-arrays of size 4 within the given array:
{3, 7, 20, 6}, {7, 20, 6, 12}, {20, 6, 12, 2}, ... , {0, 99, 5, 16}
and the max element of these, respectively, is 20, 20, 20, ..., 99 which 
are read into the resulting array. 

Now here is my problem: I know how to implement this in O (n ^ 2) complexity, but I want to make it faster so that it can be O (n), or if this is not possible, O (nlog (n)). Does anyone know if there is a faster way to do this, and if so, how?

Answer 1

-, O (k (n-k + 1)) ( O (kn)), ( ^ 2). , (n-k + 1), k.

, , memoization, k, maximums. .

maximums. "" , - .

, ( k) , maximums, : maximums[i] maximums[i-1]. , maximums, , .

maximums . , "" ( ) .

, :

#include <vector>
#include <iostream>

int main()
{
    const int window_size = 4;
    std::vector<int> vals = { 3, 7, 20, 6, 12, 2, 0, 99, 5, 16 };
    std::vector<int> maximums( window_size );
    int mhead = 0, mtail = 0;

    for( int i = 1; i < vals.size(); i ++ )
    {
        // Clean out expired maximum.
        if( maximums[mhead] + window_size <= i )
        {
            int next_mhead = (mhead + 1) % window_size;
            if( mtail == mhead ) mtail = next_mhead;
            mhead = next_mhead;
        }

        if( vals[i] >= vals[ maximums[mtail] ] )
        {
            // Replace and bubble up a new maximum value.
            maximums[mtail] = i;
            while( mhead != mtail && vals[ maximums[mtail] ] >= vals[ maximums[(mtail+window_size-1)%window_size] ] )
            {
                int prev_mtail = (mtail + window_size - 1) % window_size;
                maximums[prev_mtail] = maximums[mtail];
                mtail = prev_mtail;
            }
        }
        else
        {
            // Add a new non-maximum.
            mtail = (mtail + 1) % window_size;
            maximums[mtail] = i;
        }

        // Output current maximum.
        if( i >= window_size - 1 )
        {
            std::cout << vals[ maximums[mhead] ] << " ";
        }
    }

    std::cout << std::endl;
    return 0;
}

...

O (n), , ( ).

, , O (2n). k - k ( ). . n/k, k kn/k .

, .

, , O (n), n. , . =)