1793. Maximum Score of a Good Subarray - Explanation

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        n, res = len(nums), 0

        for i in range(k + 1):
            minEle = nums[i]
            for j in range(i, n):
                minEle = min(minEle, nums[j])
                if j >= k:
                    res = max(res, minEle * (j - i + 1))

        return res

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        n, res = len(nums), 0
        arr = nums[:]

        for i in range(k - 1, -1, -1):
            arr[i] = min(arr[i], arr[i + 1])
        for i in range(k + 1, n):
            arr[i] = min(arr[i], arr[i - 1])

        left_arr = arr[:k+1]
        right_arr = arr[k:]

        def find_right(target):
            lo, hi = 0, len(right_arr) - 1
            pos = 0
            while lo <= hi:
                mid = (lo + hi) // 2
                if right_arr[mid] >= target:
                    pos = mid
                    lo = mid + 1
                else:
                    hi = mid - 1
            return pos

        for minVal in set(arr):
            l = bisect_left(left_arr, minVal)
            r = find_right(minVal)
            res = max(res, minVal * (k - l + 1 + r))
        return res

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        n, res = len(nums), 0

        for i in range(k - 1, -1, -1):
            nums[i] = min(nums[i], nums[i + 1])
        for i in range(k + 1, n):
            nums[i] = min(nums[i], nums[i - 1])

        def find_left(target):
            lo, hi = 0, k
            while lo <= hi:
                mid = (lo + hi) // 2
                if nums[mid] < target:
                    lo = mid + 1
                else:
                    hi = mid - 1
            return lo

        def find_right(target):
            lo, hi = k, n - 1
            while lo <= hi:
                mid = (lo + hi) // 2
                if nums[mid] >= target:
                    lo = mid + 1
                else:
                    hi = mid - 1
            return hi

        for minVal in set(nums):
            i = find_left(minVal)
            j = find_right(minVal)
            res = max(res, minVal * (j - i + 1))
        return res

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        n, res = len(nums), 0
        stack = []

        for i in range(n + 1):
            while stack and (i == n or nums[stack[-1]] >= nums[i]):
                mini = nums[stack.pop()]
                j = stack[-1] if stack else -1
                if j < k < i:
                    res = max(res, mini * (i - j - 1))
            stack.append(i)

        return res

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        l = r = k
        res = nums[k]
        cur_min = nums[k]

        while l > 0 or r < len(nums) - 1:
            left = nums[l - 1] if l > 0 else 0
            right = nums[r + 1] if r < len(nums) - 1 else 0

            if left > right:
                l -= 1
                cur_min = min(cur_min, left)
            else:
                r += 1
                cur_min = min(cur_min, right)

            res = max(res, cur_min * (r - l + 1))

        return res