1793

1793. Maximum Score of a Good Subarray (Hard)

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

Companies: Google

Related Topics:
Array, Two Pointers, Binary Search, Stack, Monotonic Stack

Similar Questions:

• Largest Rectangle in Histogram (Hard)

Hints:

• Try thinking about the prefix before index k and the suffix after index k as two separate arrays.
• Using two pointers or binary search, we can find the maximum prefix of each array where the numbers are less than or equal to a certain value

Solution 1. Greedy + Two Pointers

Use a window [i + 1, j - 1] starting from [k, k] and extend it to the length of A.

The length of the window will mono-increase with the same amount = 1 in either direction, so we just always pick the direction which has a greater min value.

If lmin == rmin, extending either direction is fine. Assume we keep extending leftwards until lmin != rmin, and in this case lmin must be < rmin, so our algorithm will start to extend rightwards.

// OJ: https://leetcode.com/problems/maximum-score-of-a-good-subarray/
// Author: github.com/lzl124631x
// 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];  // `i` and `j` point to the next left and right element to extend, respectively. `mn` is the min value within window `[i + 1, j - 1]`.
        for (int len = 2; len <= N; ++len) {
            int lmin = min(mn, i >= 0 ? A[i] : 0); // if extending leftwards, the new min value is lmin
            int rmin = min(mn, j < N ? A[j] : 0); // if extending rightwards, the new min value is rmin
            if (lmin >= rmin) --i; // extending leftwards is as good as or better than extending rightwards.
            else ++j;
            mn = max(lmin, rmin);
            ans = max(ans, mn * len);
        }
        return ans;
    }
};

Solution 2. Greedy + Two Pointers

Similar to Solution 1, but we just look at the A[i] and A[j] themselves. We always pick the greater one.

This works because the min value in the window can only decrease but not increase, so picking the smaller one must yield a result that is no better than picking the greater one.

// OJ: https://leetcode.com/problems/maximum-score-of-a-good-subarray/
// Author: github.com/lzl124631x
// 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;
    }
};