MAXI - Get higher and higher
You are travelling to Kullu Manili, a hill station in India. You saw some huge mountains and very curious to climb the highest ones. Assume that there are n mountains of height hi given.
But you were wondering about what could be the total height i need to climb if I climb only the mountain of maximum height only in a segment of k continuous mountains, considering all k segements possible. You want to calculate this for all k, such that 1<=k<=n.
Mathematically, we need to find the sum of maximum element in each possible continuous segment of size k.
The first line contains an input n.
Then n numbers follow, denoting the height of ith mountain.
Output n lines, where ith line contains the sum of height of mountains to climb considering all continuous segments of size i.
5 3 4 2 3 Output: 17
For k=1, all the contiguous segments are (5), (3), (4), (2), (3). The total sum of maximum in each segment is 17 (5+3+4+2+3).
For k=2, all the contiguous segments are (5,3), (3,4), (4,2), (2,3). The total sum of maximum in each segment is 16 (5+4+4+3).
For k=3, all the contiguous segments are (5,3,4), (3,4,2), (4,2,3). The total sum of maximum in each segment is 13 (5+4+4).
For k=4, all the contiguous segments are (5,3,4,2), (3,4,2,3). The total sum of maximum in each segment is 9 (5+4).
For k=5, all the contiguous segments are (5,3,4,2,3). The total sum of maximum in each segment is 5 (5).
can we solve better than n^2? any O(n) solution.
very nice problem. can be solved using stack
weak test data :P ...
i am able to run code on my machine for number of cases,also able to run on Ideone.com,but getting wrong answer.
Last edit: 2016-02-27 09:08:45
any hint to solve it in O(n)????
What is the constraint on height? Is it in thousands, millions or billions?
I got it O(n) :)