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.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5int maximumScore(vector<int>& nums, int k) {
6 int n = nums.size();
7 int left = k, right = k;
8 int min_val = nums[k];
9 int max_score = 0;
10
11 while (left >= 0 || right < n) {
12 while (left >= 0 && (right == n || nums[left] >= nums[right])) {
13 min_val = min(min_val, nums[left--]);
14 }
15 while (right < n && (left < 0 || nums[right] > nums[left])) {
16 min_val = min(min_val, nums[right++]);
17 }
18 max_score = max(max_score, min_val * (right - left - 1));
19 }
20
21 return max_score;
22}In this C++ solution, we use two pointers left and right to expand from k, recalculating the minimum value in the subarray and updating the score as we iterate. The subarray is expanded to include more elements until the maximum possible score is achieved.
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.