Sum Of Maximum's of all contigous sub-arrays of length k of a given Array.
Difference between en4 and en5, changed 10 character(s)
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 (](http://www.spoj.com/problems/MAXI) problem.↵
Any help is appreciated.↵
Thanks :)

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)