Maximum Score of a Good Subarray LeetCode solution in Python

1
class Solution:
2
    def nextSmallerElement(self, nums):
3
        nextSmaller = [None] * len(nums)
4
        stack = [[-sys.maxsize, -1]]
5
        for i in range(len(nums) - 1, -1, -1):
6
            while nums[i] <= stack[-1][0]:
7
                stack.pop()
8
            nextSmaller[i] = stack[-1][1]
9
            stack.append([nums[i], i])
10
        return nextSmaller
11

12
    def previousSmallerElement(self, nums):
13
        previousSmaller = [None] * len(nums)
14
        stack = [[-sys.maxsize, -1]]
15
        for i in range(len(nums)):
16
            while nums[i] <= stack[-1][0]:
17
                stack.pop()
18
            previousSmaller[i] = stack[-1][1]
19
            stack.append([nums[i], i])
20
        return previousSmaller
21

22
    def maximumScore(self, nums: List[int], k: int) -> int:
23
        nextSmaller = self.nextSmallerElement(nums)
24
        previousSmaller = self.previousSmallerElement(nums)
25

26
        score = 0
27
        for idx, num in enumerate(nums):
28
            # 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)
29
            i = previousSmaller[idx]
30
            i += 1
31
            j = nextSmaller[idx]
32
            if j == -1:
33
                j = len(nums)
34
            j -= 1
35
            if i <= k <= j:
36
                score = max(score, num * (j - i + 1))
37

38
        return score