NeetCode #825LC-1793HardGreedy
← Back to All Problems#825 · #1793 · Maximum Score of a Good Subarray(好子数组的最大分数)
📌 Problem Statement & Constraints
You are given an array
nums and an integer k. A good subarray is one that contains index k. The score of a subarray is its minimum value multiplied by its length. Return the maximum score over all good subarrays. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 2 * 10^4, 0 <= k < nums.length.💡 Core Algorithmic Approaches
- Every good subarray must contain index
k, so start from the single-element window[k, k]and expand outward. - The score is
min(window) * length; the minimum only decreases as the window grows, while the length increases. - Greedily expand toward the neighbour with the larger value: taking the larger side delays a decrease in the minimum.
- Recording the score after every expansion covers all candidate windows, and the two-pointer argument is optimal because any window is reachable by a sequence of expansions.
💻 Benchmark Python3 Implementation
class Solution:
def maximumScore(self, nums: List[int], k: int) -> int:
n = len(nums)
lo = hi = k
cur_min = nums[k]
ans = nums[k]
while lo > 0 or hi < n - 1:
left = nums[lo - 1] if lo > 0 else -1 # virtual -inf sentinel
right = nums[hi + 1] if hi < n - 1 else -1
if left >= right:
lo -= 1
cur_min = min(cur_min, nums[lo])
else:
hi += 1
cur_min = min(cur_min, nums[hi])
ans = max(ans, cur_min * (hi - lo + 1))
return ans⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each index enters the window exactly once.
💾 Space Complexity
O(1): two pointers and a running minimum.
⚠️ Interview Pitfalls & Follow-ups
- Expanding toward the smaller neighbour: that drops the minimum earlier; always take the larger side to preserve the current minimum as long as possible.
- Comparing
min * lengthonly at the end: the optimum can occur at any window size, so the score must be recorded after every expansion. - Using 0 as the boundary sentinel: values are positive, but a
-1sentinel is the safe choice so an exhausted side is never selected. - Restarting the minimum from scratch: the running minimum must persist across expansions, since the window only grows.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.