Leetcode 1793: Maximum Score of a Good Subarray

In this problem, we are trying to optimize the “score” of “good subarrays defined this way:

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.

Solution

The brute force approach for this would be to try all the pairs (i,j) such that i <= k <= j. Assuming that we can optimize and get the minimum value in O(1) average time, the algorithm would be O(n²) with n the size of the array.

How to improve this to a more scalable algorithm? Which of the scores don’t need to be computed? First, we can notice that given i <= k , with min(nums[i..k]) = m, we can directly pick j such that nums[j+1] < m.

In the algorithm, we iteratively build optimal good subarrays, which are optimal in the sense that, for s from 1 to n, we build one good subarray of size s that has the maximum score for all good subarrays of size s. Once we do that, we only need to select the best score out of these n scores.

To build a good subarray of size s with maximum score, we only need to select one such that the minimum in the array is the greatest possible (a max min), because the size of the good subarray is fixed.