Towers Without a Valley - Google Top Interview Questions

                        Solution in C++ :

vector<int> calc(vector<int> a) {
    int i, n = a.size(), sum = 0;
    vector<int> ret(n, 0);
    vector<pair<int, int>> st;
    for (i = 0; i < n; i++) {
        int count = 1;
        sum += a[i];
        while (st.size() && st.back().first >= a[i]) {
            int num = st.back().first, freq = st.back().second;
            count += freq;
            sum -= (num - a[i]) * freq;
            st.pop_back();
        }
        st.emplace_back(a[i], count);
        ret[i] = sum;
    }
    return ret;
}

int solve(vector<int>& nums) {
    vector<int> left = calc(nums);
    reverse(nums.begin(), nums.end());
    vector<int> right = calc(nums);
    int ret = 0, i, n = nums.size();
    for (i = 0; i < n; i++) ret = max(ret, left[i] + right[n - i - 1] - nums[n - 1 - i]);
    return ret;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[] nums) {
        int n = nums.length;
        int[] left = getIncreasingSum(nums);
        int[] right = reverse(getIncreasingSum(reverse(nums)));
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, left[i] + right[i] - nums[i]);
        }

        return max;
    }

    int[] reverse(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) res[n - 1 - i] = nums[i];
        return res;
    }
    int[] getIncreasingSum(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Deque<Integer> dq = new ArrayDeque();
        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!dq.isEmpty() && nums[dq.peekLast()] > nums[i]) {
                int idx = dq.pollLast();
                int count = !dq.isEmpty() ? idx - dq.peekLast() : idx + 1;
                int diff = nums[idx] - nums[i];
                total = total - (diff * count);
            }
            total += nums[i];
            dq.addLast(i);
            res[i] = total;
        }
        return res;
    }
}
                    

                        Solution in Python : 
                            
# Solves "half" of the problem:
# For each prefix `P` of `nums`, find the increasing sequence bounded by `P`
# with the maximum sum, and return that sum.
def increasing_prefix_sums(nums):
    # Store the current best increasing sequence, in the form (value, number of occurrences)
    stack = []
    current_sum = 0  # always equal to sum(x * c for x in stack)

    ans = []

    for x in nums:
        count = 1

        # We need to include `x` in our sequence. Values to the left may need to be reduced.
        while stack and stack[-1][0] > x:
            # Anything greater than `x` gets clamped down to `x`.
            # Since `stack` is increasing we only need to look at its tail.
            # This is similar to the min-queue algorithm.
            current_sum -= stack[-1][0] * stack[-1][1]
            count += stack[-1][1]
            stack.pop()

        stack.append((x, count))
        current_sum += x * count
        ans.append(current_sum)

    return ans


class Solution:
    def solve(self, nums):
        left = increasing_prefix_sums(nums)
        right = reversed(increasing_prefix_sums(reversed(nums)))
        # left[i] + right[i] overcounts by nums[i], so subtract that out
        return max(l + r - x for l, r, x in zip(left, right, nums))