We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Score of a Good Subarray

Difficulty: Hard

Problem Description

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.

Key Insights

  • A subarray must include the index k.
  • The score is determined by the minimum value in the subarray multiplied by its length.
  • To maximize the score, we need to efficiently find the minimum value over varying lengths of subarrays that include k.
  • The problem can be approached using techniques such as a monotonic stack to efficiently find boundaries for valid subarrays.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use a monotonic stack to find the boundaries of the good subarrays that include the index k. The idea is to calculate the "left" and "right" boundaries for the subarrays that can be formed with k as the center. The minimum value in the subarray is determined by the value at index k and the lengths of the good subarrays are calculated based on these boundaries. By iterating through the array and using the stack to maintain the minimums, we can efficiently compute the maximum score.

Code Solutions

def maximumScore(nums, k):
    n = len(nums)
    left = [0] * n
    right = [0] * n
    
    # Finding the left boundary
    stack = []
    for i in range(n):
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    
    # Clear the stack to reuse for right boundary
    stack = []
    # Finding the right boundary
    for i in range(n-1, -1, -1):
        while stack and nums[stack[-1]] > nums[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)
    
    max_score = 0
    # Calculate the score for subarrays including k
    for i in range(n):
        if left[i] < k < right[i]:  # Check if k is within bounds
            score = nums[i] * (right[i] - left[i] - 1)
            max_score = max(max_score, score)
    
    return max_score
← Back to All Questions