<p>You are given an array of integers <code>nums</code> <strong>(0-indexed)</strong> and an integer <code>k</code>.</p>

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

<p>Return <em>the maximum possible <strong>score</strong> of a <strong>good</strong> subarray.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>0 &lt;= k &lt; nums.length</code></li>
</ul>

'''
so k is basically a "partition" or a barrier that your two ends cant cross
and you're trying to find the maximum distance you can separat ethe two
to maximize the score. where of coruse if you take in more elements
you're more likely to encounter a smaller value and so a lower score
but so long as the min stays the same you do want to just extend
as far as you can and since order matters you cant sort

bf approach is of course to just try subarrays N^2
we can also cache the running min for example
heres something to observe, starting from that index going outwards
we know the subarray has to be growing like that
now if you encounter a larger or == value to the current min going left or right
you know its only optimal to take those values

could you take it greedily?
so you look at left and right
if the left is >= keep going left 
if right is >= keep going right
then you have a point where either oob or the left right value is a new min
save possible score excluding the two new ones
then you look at the smaller (actually greater) between the two and take that as your new min
and repeat keep expanding so if left is >= keep taking
if right is >= keep taking etc 
surely thats optimal
'''
'''
lol thats the first time I got a greedy correct
though not completely you said min of the two, but you actually want the max
of course so you maximize the score first duh 

but we're finding the maximum minimum distance where the min stays the same
so thats a maximin problem ie binary search works 

then theres also a montonic stack solution to find the closest smaller value
to the left and right
1) binary search
2) monotonic stack
3) greedy
'''
'''
1) binary search:.. need thinking

2) monotonic stack makses sense 
    we're treating each element as if it were the min
    then finding the closest smaller left and closest smaller right
    check theyre across k (satisfy constraint) and if so calculate the score
    thats a linear time algo to get closest left and right with mono stack
    and linear time to calculate score 
    O(N) O(N)

again though 2) is hinged on realizing we can keep taking >= values 
and that will only be optimal
'''
#greedy?
class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        max_score = 0
        left, right = k, k
        running_min = nums[k]
        while left >= 0 or right < len(nums):
            #keep taking left
            while left >= 0 and nums[left] >= running_min:
                left -= 1

            #keep taking right
            while right < len(nums) and nums[right] >= running_min:
                right += 1

            #update score
            distance = right - left - 1
            max_score = max(max_score, distance * running_min)

            #choose max of left or right as next min
            left_value = nums[left] if left >= 0 else -inf
            right_value = nums[right] if right < len(nums) else -inf
            running_min = max(left_value, right_value)

        return max_score
        
761