subarray is a subarray where i <= k <= j.

Return the maximum possible score of a good subarray.

Examples

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.

Solution

Method 1 - Two Pointer Technique

We need to find the subarray that includes the index k (from i to j where i <= k <= j) and maximizes the score defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1).

Here is the approach:

Start with the subarray that only contains the element at index k.
Expand the subarray to the left and right, one element at a time, while keeping track of the minimum element in the subarray.
For each expansion, calculate the score and keep track of the maximum score encountered.

Code

[{"language":"Java","code":"public class

Related Tags