Maximum Score of a Good Subarray
01 · Problem
You are given an integer array nums (0-indexed) and an index k.
The score of a subarray nums[i..j] is min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1). A subarray is good if it contains index k, that is i <= k <= j.
Return the highest score of any good subarray.
02 · Examples
nums = [1,4,3,7,4,5], k = 3
15
The subarray from index 1 to 5 is [4,3,7,4,5]. Its minimum is 3 and its length is 5, so its score is 15.
nums = [5,5,4,5,4,1,1,1], k = 0
20
The subarray from index 0 to 4 is [5,5,4,5,4], with minimum 4 and length 5, for a score of 20.
nums = [2,6,1,8,8], k = 4
16
The subarray [8,8] at indices 3 to 4 has minimum 8 and length 2, for a score of 16. Extending further left pulls the minimum down to 1.
03 · Constraints
- 011 <= nums.length <= 105
- 021 <= nums[i] <= 2 * 104
- 030 <= k < nums.length
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.