Sum Of Maximum's of all contigous sub-arrays of length k of a given Array.

Revision en6, by akshit.lite, 2016-02-15 06:46:36

I have been thinking of an algorithm which could find the Sum Of Maximum's of all contigous sub-arrays of length k of a given Array. for each k from 1 to n , seperatly. n is the length of the array. I am able to figure out an O(N^2) solution. But could not reduce the complexity further. It would be helpful if someone could tell a sub-quadratic approach.(Possibly O(n) ). This is in reference to this problem. Any help is appreciated. NOTE : the answer for each k has to be printed seperately. Thanks :)

Tags spoj, algorithms, help, compettive programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English akshit.lite 2016-02-15 06:46:36 60
en5 English akshit.lite 2016-02-15 00:48:43 10 Tiny change: 'erence to this (www.spoj.c' -> 'erence to [this](http://www.spoj.c'
en4 English akshit.lite 2016-02-15 00:47:34 3 Tiny change: 'erence to [this](www.spoj.' -> 'erence to this (www.spoj.'
en3 English akshit.lite 2016-02-15 00:46:41 8 Tiny change: 'rence to [THIS](www.spoj' -> 'rence to [this](www.spoj'
en2 English akshit.lite 2016-02-15 00:45:32 1 Tiny change: 'lems/MAXI)problem.\n' -> 'lems/MAXI) problem.\n'
en1 English akshit.lite 2016-02-15 00:41:42 559 Initial revision (published)