⚡Flashcard Drill➔
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

  1. Every good subarray must contain index k, so start from the single-element window [k, k] and expand outward.
  2. The score is min(window) * length; the minimum only decreases as the window grows, while the length increases.
  3. Greedily expand toward the neighbour with the larger value: taking the larger side delays a decrease in the minimum.
  4. 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 * length only 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 -1 sentinel 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems