Hi there

I solved the problem in 2 stages:

1) identify which index should be the peak

2) constructing the optimal height given the fact that that index is the peak

Here's how I arrived at that intuition:

1) for an index i, either all skyscrapers to the left are shorter, or all skyscrapers to the right are shorter, or both

2) if you keep moving to the taller neighbouring skyscraper (either left or right), you will eventually reach the tallest

3) so there will be a tallest skyscraper which is limited by m[i]

If you want to solve C1 (n <= 1000), you can do it in O(n^2) time by trying each index. For each index, try to reconstruct the ideal height profile. From that index, iterate to the left and maintain the current minimum height. Set the height to that min height. Do the same for the index to the right. Then calculate the total height. If it is higher than the other "top indexes" you have tried so far, save this height profile.

My solution to C1: 129472475

If you want to solve C2 (n<=500000), you need to check the sum faster without constructing the heights. It is possible by maintaining a prefixSum and suffixSum array that obeys the "increasing then decreasing" profile. Basically for each index, you search left (prefixSum) or right (suffixSum) for the next point where m[searchIdx] is first smaller than m[i]. You can use RMQ and binary search (129470333 TLED because python is slow) to do each search in O(log(n)) time, or use an increasing stack (129471345) in O(1) time. After you've found the searchIdx, all "cnts" terms from i to just before searchIdx are set to h[i] (it cannot be more). Then you add the prefixSum[searchIdx] or suffixSum[searchIdx] to cnts*h[i] to get prefixSum[i] or suffixSum[i]. Then you can iterate for all indexes to find which index, when set to the tallest index, gives the most height. Finally, you can reconstruct the heights in the same manner I've described for C1 above.

Hope this helps.