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.

  • 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