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.
1import java.util.Stack;
2
3
This Java implementation uses infix traversals and tracks potential boundaries of minimal elements. With left and right arrays, we define valid subarray bounds, ensuring it includes k and updating the max score accordingly.