maximum-score-good-subarray

Answer

Key insight: The score is min × width. To maximize it, you want to keep the window's minimum as high as possible while growing it — so always expand toward the larger neighbor. Starting from [k, k], each expansion picks the bigger of nums[i-1] and nums[j+1]; the running min then degrades as slowly as possible, and every intermediate window is a valid candidate. This runs in O(n) time, O(1) space.

Tricky boundaries to handle: 1. One side hits the array edge — you must keep expanding the other side (i == 0 → only j++; j == n-1 → only i--). 2. After an expansion, only the newly added element can lower the min — but since the window is always contiguous and contains k, updating against both nums[i] and nums[j] is safe and simple (one is new, the other was already inside). 3. The empty-window case can't occur: the window starts as [k, k], so the answer is always at least nums[k].

// maximumScore returns the max score over all subarrays containing nums[k],
// where score = min(nums[i..j]) * (j-i+1).  O(n) time, O(1) space.
func maximumScore(nums []int, k int) int {
    n := len(nums)
    minVal := nums[k]
    ans := minVal
    i, j := k, k
    for i > 0 || j < n-1 {
        // Expand toward the larger neighbor so minVal falls as slowly as possible.
        if i == 0 {
            j++
        } else if j == n-1 {
            i--
        } else if nums[i-1] < nums[j+1] {
            j++
        } else {
            i--
        }
        // The newly added element is at i or at j; the other index was
        // already inside the window, so it cannot raise minVal.
        if nums[i] < minVal {
            minVal = nums[i]
        }
        if nums[j] < minVal {
            minVal = nums[j]
        }
        if c := minVal * (j - i + 1); c > ans {
            ans = c
        }
    }
    return ans
}

Why the greedy is correct: The window's min is monotonically non-increasing as it grows. Taking the smaller neighbor first lowers min at least as much as taking the larger neighbor first, but cannot ever lead to a wider reachable window with the same min — any optimal window [L, R] with min m is exactly the one the greedy visits when it keeps taking the larger side until that window closes. Every candidate window is evaluated, so the max is captured. (Alternative O(n) formulation: monotonic stack over "nearest smaller element" per index, scoring each index's maximal min-domain that contains k — same result, more code.)