Problem statement

https://binarysearch.com/problems/Towers-Without-a-Valley/

Solution

First notice, that we need to find the mountain array which is less than equal that ours, that is it have a structure: increasing part, decreasing part (one of the parts can be empty). Let us answer the question: for every index try to make it mountain peak. Let us go from left to right and keep in our stack indexes of increasing elements. In lft we will keep cumulative sums. Then to update lft[i] we need to look at previous element in our stack and repeat M[i] (i - stack[-1]) times.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, M):
        n = len(M)
        lft, rgh = [0]*(n + 1), [0]*(n + 1)
        stack = [-1]
        for i in range(n):
            while len(stack) > 1 and M[stack[-1]] >= M[i]: stack.pop()
            lft[i] = lft[stack[-1]] + (i - stack[-1]) * M[i]
            stack += [i]

        stack = [n]
        for i in range(n - 1, -1, -1):
            while len(stack) > 1 and M[stack[-1]] >= M[i]: stack.pop()
            rgh[i] = rgh[stack[-1]] + (stack[-1] - i) * M[i]
            stack += [i]

        return max(lft[i] + rgh[i] - M[i] for i in range(n))