You are given an array of integers nums (0-indexed) and an integer k.

The score of a subarray (i, j) is defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1). A good subarray is a subarray where i &lt;= k &lt;= j.

Return the maximum possible score of a good subarray.

&nbsp;
Example 1:

Input: nums = [1,4,3,7,4,5], k = 3
Output: 15
Explanation: The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15. 


Example 2:

Input: nums = [5,5,4,5,4,1,1,1], k = 0
Output: 20
Explanation: The optimal subarray is (0, 4) with a score of min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20.


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 105
	1 &lt;= nums[i] &lt;= 2 * 104
	0 &lt;= k &lt; nums.length


class Solution:
    def nextSmallerElement(self, nums):
        nextSmaller = [None] * len(nums)
        stack = [[-sys.maxsize, -1]]
        for i in range(len(nums)-1, -1, -1):
            while nums[i] <= stack[-1][0]:
                stack.pop()
            nextSmaller[i] = stack[-1][1]
            stack.append([nums[i], i])
        return nextSmaller
            
    
    def previousSmallerElement(self, nums):
        previousSmaller = [None] * len(nums)
        stack = [[-sys.maxsize, -1]]
        for i in range(len(nums)):
            while nums[i] <= stack[-1][0]:
                stack.pop()
            previousSmaller[i] = stack[-1][1]
            stack.append([nums[i], i])
        return previousSmaller
    
    def maximumScore(self, nums: List[int], k: int) -> int:
        nextSmaller = self.nextSmallerElement(nums)
        previousSmaller = self.previousSmallerElement(nums)

        score = 0
        for idx, num in enumerate(nums):
			# previousSmaller[idx] (let's say i) and nextSmaller[idx] (let's say j) ensures that the element present at idx is the minimum in range (i -> j)
            i = previousSmaller[idx]
            i += 1
            j = nextSmaller[idx]
            if j == -1:
                j = len(nums)
            j -= 1
            if i <= k <= j:
                score = max(score, num * (j-i+1))
        
        return score
            
class Solution {
    public int maximumScore(int[] nums, int k) {
        int n = nums.length;
        int i = k - 1, j = k + 1;
        int min = nums[k];
        int ans = min;

        while(i >= 0 || j < n) {
            int v1 = 0, v2 = 0;
            int min1 = min, min2 = min;

            if(i >= 0) {
                min1 = Math.min(min, nums[i]);
                v1 = min1 * (j - i);
            }

            if(j < n) {
                min2 = Math.min(min, nums[j]);
                v2 = min2 * (j - i);
            }

            if(v1 > v2) {
                --i;
                ans = Math.max(v1, ans);
                min = Math.min(min1, min);
            }
            else {
                ++j;
                ans = Math.max(ans, v2);
                min = Math.min(min, min2);
            }
        }

        return ans;
    }
}
class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        nums.push_back(0);
        stack<int> st ;
        int n = nums.size(), res = 0;
        for(int i=0; i<n ; i++){
            while(!st.empty() && nums[st.top()] >= nums[i]){
                int height = nums[st.top()];
                st.pop();
                int left = st.empty() ? -1: st.top();
                if(k < i && k > left) res = max(height* (i-left-1), res);
            }
            st.push(i);
        }
        return res;
    }
};
/*

	JAVASCRIPT

 */
var maximumScore = function(nums, k) {
    // iterate to the left to update the minimum value at each index
    let min = nums[k];
    for (let i = k - 1; i >= 0; i--) {
        min = Math.min(min, nums[i]);
        nums[i] = min;
    }

    // iterate to the right to update the minimum value at each index
    min = nums[k];
    for (let i = k + 1; i < nums.length; i++) {
        min = Math.min(min, nums[i]);
        nums[i] = min;
    }
    
    // start with 2 pointers at opposite ends of nums
    let left = 0;
    let right = nums.length - 1;
    let bestScore = 0;

    while (left <= right) {
        bestScore = Math.max(bestScore, Math.min(nums[left], nums[right]) * (right - left + 1));
        
        // first to check if either pointer is at k
        // if it is at k then we must move the other pointer inwards
        if (left === k) {
            right--;
        } else if (right === k) {
            left++
            
        // if neither index is at k move the pointer
        // that is smaller inwards
        } else if (nums[left] < nums[right]) {
            left++;
        } else {
            right--;
        }
    }
    return bestScore;
};
Maximum Score of a Good Subarray