Solving Algorithmic Problems

Description   Solution: Monotonic Increasing Stack Find the maximum possible sum of heights ending and starting at each index  i . left :  left[i]  = sum of heights from ( 0, ..., i ) such that they are descending from index  i  to  0 . right :  right[i]  = sum of heights from ( i, ..., n - 1 ) such that they are descending from index  i  to  n - 1 . Use a monotonic increasing stack to store indices of  maxHeights  such that they are smaller than  maxHeights[i] . left to right: We know that from index  i  to  stack[stack.length - 1] , all heights are smaller than  maxHeights[i] . Take the existing sum up to  stack[stack.length - 1]  ( left[stack[stack.length - 1]] ) and add the sum for the current range ( maxHeights[i] * (i - stack[stack.length - 1]) ) Then, do the same from right to left. Take each  maxHeights[i]  as the peak of the mountain and use the results from  ...

Description   Solution 1: Brute Force Try to take each position as the peak. From the peak, iterate to the left and right and calculate the sum of heights ensuring that the heights on the left of the peak and right of the peak decrease/are equal. Time Complexity:  O(n^2) Space Complexity:  O(1) var maximumSumOfHeights = function ( maxHeights ) { let n = maxHeights.length, maxSum = 0 ; for ( let i = 0 ; i < n; i++) { let peak = maxHeights[i], currHeight = peak, sum = peak; for ( let j = i - 1 ; j >= 0 ; j--) { currHeight = Math .min(currHeight, maxHeights[j]); sum += currHeight; } currHeight = peak; for ( let j = i + 1 ; j < n; j++) { currHeight = Math .min(currHeight, maxHeights[j]); sum += currHeight; } maxSum = Math .max(maxSum, sum); } return maxSum; }; Solution 2: Monotonic Increasing Stack Find the maximum possible sum of heights ending and starting at each index  i . left :  lef...