Maximum Score of a Good Subarray

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⁵
1 <= nums[i] <= 2 * 10⁴
0 <= k < nums.length

Approaches

Checkout 2 different approaches to solve Maximum Score of a Good Subarray. Click on different approaches to view the approach and algorithm in detail.

Brute Force over Good Subarrays

The most straightforward approach is to check every possible "good" subarray. A subarray (i, j) is considered good if it contains the index k, which means i <= k <= j. We can use nested loops to generate all such subarrays, calculate their scores, and keep track of the maximum score.

Algorithm

Initialize maxScore to 0.
Iterate through all possible start indices i from 0 to k.
For each i, start an inner loop for all possible end indices j from k to n-1.
For each pair of (i, j), we have a "good" subarray.
To calculate the score, find the minimum element currentMin in the subarray nums[i...j].
Calculate the score as currentMin * (j - i + 1).
Update maxScore with the maximum score found so far.
To avoid a third loop which would make the complexity O(N^3), we can optimize finding the minimum. For a fixed i, as j increases, we can update the minimum in O(1) time.
The refined algorithm iterates i from 0 to k. For each i, it calculates the minimum from i to k, then extends to the right towards n-1, updating the minimum and score at each step.

This method involves a brute-force check of all valid subarrays. We can set up two nested loops: the outer loop iterates through all possible start indices i from 0 to k, and the inner loop iterates through all possible end indices j from k to n-1.

A naive implementation would find the minimum of nums[i...j] in a third loop, leading to an O(N^3) complexity. We can optimize this to O(N^2) by noticing that for a fixed start i, as we expand the end j, the minimum of the subarray can be updated incrementally.

Here is the O(N^2) algorithm:

Initialize maxScore = 0.
Loop i from 0 to k.
Initialize min_i_to_k by finding the minimum in nums[i...k].
Loop j from k to n-1.
In this loop, update the overall minimum for nums[i...j] based on the previous minimum and nums[j].
Calculate the score for (i, j) and update maxScore.

class Solution {
    public int maximumScore(int[] nums, int k) {
        int n = nums.length;
        int maxScore = 0;

        // Iterate through all possible start indices i <= k
        for (int i = 0; i <= k; i++) {
            int currentMin = nums[k];
            // Find minimum in the left part of the subarray [i, k]
            for (int p = k; p >= i; p--) {
                currentMin = Math.min(currentMin, nums[p]);
            }

            // Now expand to the right part [k, j]
            // The minimum from i to k is already computed in currentMin
            int minForSubarray = currentMin;
            for (int j = k; j < n; j++) {
                minForSubarray = Math.min(minForSubarray, nums[j]);
                int score = minForSubarray * (j - i + 1);
                maxScore = Math.max(maxScore, score);
            }
        }
        return maxScore;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the length of the `nums` array. The outer loop runs `k+1` times, and the inner loops combined run in `O(N)` time for each `i`, leading to a total complexity of `O(k*N)`, which is `O(N^2)` in the worst case.Space Complexity: O(1), as we only use a constant amount of extra space for variables.

Pros and Cons

Pros:

It's relatively simple to understand and implement.
It correctly explores all possibilities and guarantees finding the optimal solution.

Cons:

This approach is too slow for the given constraints (N up to 10^5) and will likely result in a 'Time Limit Exceeded' error on most platforms.

Code Solutions

Checking out 3 solutions in different languages for Maximum Score of a Good Subarray. Click on different languages to view the code.

class Solution { public int maximumScore ( int [] nums , int k ) { int n = nums . length ; int [] left = new int [ n ]; int [] right = new int [ n ]; Arrays . fill ( left , - 1 ); Arrays . fill ( right , n ); Deque < Integer > stk = new ArrayDeque <>(); for ( int i = 0 ; i < n ; ++ i ) { int v = nums [ i ]; while (! stk . isEmpty () && nums [ stk . peek ()] >= v ) { stk . pop (); } if (! stk . isEmpty ()) { left [ i ] = stk . peek (); } stk . push ( i ); } stk . clear (); for ( int i = n - 1 ; i >= 0 ; -- i ) { int v = nums [ i ]; while (! stk . isEmpty () && nums [ stk . peek ()] > v ) { stk . pop (); } if (! stk . isEmpty ()) { right [ i ] = stk . peek (); } stk . push ( i ); } int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( left [ i ] + 1 <= k && k <= right [ i ] - 1 ) { ans = Math . max ( ans , nums [ i ] * ( right [ i ] - left [ i ] - 1 )); } } return ans ; } }

Video Solution

Watch the video walkthrough for Maximum Score of a Good Subarray

Algorithms:

Binary Search

Patterns:

Two Pointers

Data Structures:

ArrayStackMonotonic Stack