https://leetcode.com/problems/maximum-score-of-a-good-subarray

Let us define by left running minimum to the left of our number k and by right running minimum to the right of index k. For example for nums = [1,4,3,7,4,5] and k = 3 we have:

left = [1,3,3,7], right = [7, 4, 4]. Here we start to build these minimum from the kth element.

Notice, that we can have only 2 options:

  1. Smallest element from nums[i], ... nums[j] will be after element with index k.
  2. Smallest element from nums[i], ... nums[j] will be before element with index k.

Let us deal with case 1. Let us now iterate through elemens elem in the the right part and for each of them find the smallest element in the left part, such that it is more or equal to elem. We can do it, using binary search. Why we need the first element? Because the smaller index i we have, the bigger will be score: min term will be equal to elem and we wan to make width as big as possible.

In exaclty the same way we deal with case 2.

Complexity: time complexity is O(n log n), because all we do it perform binary search O(n) times. Space complexity is O(n).

class Solution:
    def maximumScore(self, nums, k):
        def test(nums, k):
            left  = list(accumulate(nums[:k+1][::-1], min))[::-1]
            right = list(accumulate(nums[k:], min))
            ans = 0
            for j in range(0, len(right)):
                i = bisect_left(left, right[j])
                if i >= 0: ans = max(ans, (k + j - i + 1) * right[j] )

            return ans

        return max(test(nums, k), test(nums[::-1], len(nums) - k - 1))

If you like the solution, you can upvote it on leetcode discussion section: Problem 1793