{x}
blog image

Maximum Score of a Good Subarray

You are given an array of integers nums (0-indexed) and an integer k.

The score of a subarray (i, j) is defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1). A good subarray is a subarray where i <= k <= j.

Return the maximum possible score of a good subarray.

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 2 * 104
  • 0 <= k < nums.length

Solution Explanation: Maximum Score of a Good Subarray

This problem asks for the maximum score of a "good" subarray, where a subarray is considered "good" if it contains index k. The score of a subarray is calculated as the minimum element within the subarray multiplied by the length of the subarray.

The optimal approach uses a monotonic stack to efficiently find the maximum score. Here's a breakdown:

1. Monotonic Stack for Range Calculation:

The core idea is to efficiently determine, for each element nums[i], the leftmost index left[i] and the rightmost index right[i] such that:

  • nums[left[i]] < nums[i] (strictly less than for the left bound)
  • nums[right[i]] <= nums[i] (less than or equal to for the right bound)

A monotonic decreasing stack is used for this. The stack maintains indices, ensuring that the elements at the top of the stack are in decreasing order.

  • Iteration 1 (Left Boundary): The algorithm iterates through the nums array. For each element, it pops elements from the stack that are greater than or equal to the current element. This ensures that the remaining element at the top of the stack (if any) represents the left boundary.
  • Iteration 2 (Right Boundary): A similar process is repeated in reverse order to find the right boundary.

2. Score Calculation and Constraint Check:

Once left[i] and right[i] are determined for each nums[i], the score is calculated as nums[i] * (right[i] - left[i] - 1). The -1 accounts for excluding left[i] and right[i] themselves from the subarray length.

Crucially, a subarray is only considered "good" if left[i] + 1 <= k <= right[i] - 1. This condition ensures that index k falls within the subarray defined by left[i] and right[i].

3. Maximum Score:

The algorithm iterates through the calculated scores and keeps track of the maximum score found.

Time Complexity: O(n) - The algorithm iterates through the array a constant number of times using the stack. Stack operations are O(1) on average. Space Complexity: O(n) - To store the left, right, and stack.

Code Examples (Python, Java, C++, Go, TypeScript):

The provided code examples in various languages demonstrate this approach. They all follow the same algorithmic steps:

  1. Initialization: Create left and right arrays and initialize them with default values (that indicate no bounds found yet).
  2. Monotonic Stack (Left): Use a stack to find the left boundary for each element.
  3. Monotonic Stack (Right): Use a stack to find the right boundary for each element.
  4. Score Calculation and Max: Iterate through the array, calculate the scores, and update the maximum score if a valid "good" subarray is found.

The code is well-structured and clearly implements the explained algorithm. The use of a monotonic stack is key to achieving the optimal linear time complexity. Each language's specific syntax is used, but the logic remains consistent across all examples.