Formatted question description: https://leetcode.ca/all/1793.html

1793. Maximum Score of a Good Subarray

Level

Hard

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.

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 <= 10^5
• 1 <= nums[i] <= 2 * 10^4
• 0 <= k < nums.length

Solution

Loop over nums and use a monotonic stack to store each element’s edges, where the elements increase from botton to top of the monotonic stack.

For each 0 <= i < nums.length, use left[i] to store the maximum j such that j < i and nums[j] < nums[i], and use right[i] to store the minimum j such that j > i and nums[j] < nums[i]. Suppose nums[-1] = nums[nums.length] = -1.

For each 0 <= i < nums.length, if right[i] > k and left[i] < k, calculate the score at index i as nums[i] * (right[i] - left[i] - 1). Maintain the maximum score and return the maximum score.

• Java
• C++
• Python

• class Solution {
      public int maximumScore(int[] nums, int k) {
          int length = nums.length;
          int[] left = new int[length];
          int[] right = new int[length];
          Arrays.fill(right, length);
          Deque<Integer> stack = new LinkedList<Integer>();
          for (int i = 0; i < length; i++) {
              while (!stack.isEmpty() && nums[stack.peek()] >= nums[i])
                  right[stack.pop()] = i;
              left[i] = stack.isEmpty() ? -1 : stack.peek();
              stack.push(i);
          }
          int score = 0;
          for (int i = 0; i < length; i++) {
              if (left[i] < k && right[i] > k)
                  score = Math.max(score, nums[i] * (right[i] - left[i] - 1));
          }
          return score;
      }
  }
  

• // OJ: https://leetcode.com/contest/weekly-contest-232/problems/maximum-score-of-a-good-subarray/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      int maximumScore(vector<int>& A, int k) {
          int i = k - 1, j = k + 1, N = A.size(), ans = A[k], mn = A[k];
          while (i >= 0 || j < N) {
              if (i < 0 || (j < N && A[j] > A[i])) {
                  mn = min(mn, A[j]);
                  ++j;
              } else {
                  mn = min(mn, A[i]);
                  --i;
              }
              ans = max(ans, mn * (j - i - 1));
          }
          return ans;
      }
  };
  

• # 1793. Maximum Score of a Good Subarray
  # https://leetcode.com/problems/maximum-score-of-a-good-subarray/
  
  class Solution:
      def maximumScore(self, nums: List[int], k: int) -> int:
          res = mini = nums[k]
          i, j, n = k, k, len(nums)
          
          while i > 0 or j < n - 1:
              if (nums[i-1] if i > 0 else 0) < (nums[j + 1] if j < n - 1 else 0):
                  j += 1
              else:
                  i -= 1
              
              mini = min(mini, nums[i], nums[j])
              res = max(res, mini * (j - i + 1))
          
          return res
  
  

All Problems

All Solutions