1793. Maximum Score of a Good Subarray (Leetcode)

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 Explanation:

• In this problem we have to choose a sub-array [i, j] where i <= k and j >= k. So we can clearly observe that, the smallest interval we can take is [k, k].
• So we start out by considering [k, k] to be the first interval (i.e i = k and j = k) and max as nums[k].
• Also we will have a variable min to store min value from i to j.

int max = nums[k]; int i = k, j = k; int min = nums[k];

• Then we will check to the left of range(i.e i - 1) and right of range(i.e j + 1).
• Then if nums[i - 1] > nums[j + 1], we will decrement i to i - 1, otherwise increment j to j + 1.
• By continuing in this way we will sequentially process all ranges greedily, which can potentially contribute to our solution.
• Also remember to handle edge cases where i == 0 and j == nums.length - 1 accordingly.

while(true) { if(i == 0 && j == nums.length - 1) { break; } if(i == 0) { j++; min = Math.min(min, nums[j]); } else if(j == nums.length - 1) { i--; min = Math.min(min, nums[i]); } else { if(nums[j + 1] > nums[i - 1]) { j++; min = Math.min(min, nums[j]); } else { i--; min = Math.min(min, nums[i]); } } max = Math.max(max, min * (j - i + 1)); }

Full Code (Java): class Solution { public int maximumScore(int[] nums, int k) { int max = nums[k]; int i = k, j = k; int min = nums[k]; while(true) { if(i == 0 && j == nums.length - 1) { break; } if(i == 0) { j++; min = Math.min(min, nums[j]); } else if(j == nums.length - 1) { i--; min = Math.min(min, nums[i]); } else { if(nums[j + 1] > nums[i - 1]) { j++; min = Math.min(min, nums[j]); } else { i--; min = Math.min(min, nums[i]); } } max = Math.max(max, min * (j - i + 1)); } return max; } }