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