Sponsored
Sponsored
This approach involves expanding the subarray to the left and right of index k using two pointers. The objective is to maintain the minimum value in the subarray which can be computed incrementally. Extend the window until further expansion leads to a reduced score.
Time Complexity: O(n), because each element is processed at most twice, once by each pointer.
Space Complexity: O(1), as we are using only a constant amount of extra space.
1def maximumScore(nums, k):
2 n = len(nums)
3 left = right = k
4 min_val = nums[k]
5 max_score = 0
6
7 while left >= 0 or right < n:
8 while left >= 0 and (right == n or nums[left] >= nums[right]):
9 min_val = min(min_val, nums[left])
10 left -= 1
11 while right < n and (left < 0 or nums[right] > nums[left]):
12 min_val = min(min_val, nums[right])
13 right += 1
14 max_score = max(max_score, min_val * (right - left - 1))
15
16 return max_scoreThis Python solution uses two pointers to expand the subarray from the index k. It continuously calculates the score for each valid subarray, updating the maximum score found. The min_val is maintained as the window expands.
This approach involves using a monotonic stack to efficiently determine the range of the smallest element in which it acts as the minimum of a subarray. Thus, it can be used to calculate the potential maximum score by determining the largest possible width for each minimum value.
Time Complexity: O(n), for constructing boundaries with stacks and iterating through the arrays.
Space Complexity: O(n), due to usage of additional arrays and stack.
1function maximumScore(nums, k) {
2
This JavaScript code uses a similar approach with a monotonic stack as the previous Java solution. It calculates the range in which each element can act as the minimum and finds the maximum score among subarrays that include index k.