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. Thanks :)