LeetCode 1793: Maximum Score of a Good Subarray

Explanation

To solve this problem, we need to find the maximum score of a good subarray where the subarray contains the element at index k.

One approach to solve this problem is to iterate over all possible subarrays with k in the middle, calculate the score for each subarray, and keep track of the maximum score found so far.

We can achieve this by using two pointers to define the subarray and then calculate the score for each subarray. The score of a subarray can be calculated as the minimum element in the subarray multiplied by the length of the subarray.

Algorithm

1. Initialize a variable n to store the length of the input array nums.
2. Initialize a variable maxScore to keep track of the maximum score found so far.
3. Iterate over all possible subarrays with element at index k in the middle:
   • Use two pointers to define the subarray [left, right] where left starts at k and right starts at k, then expands in both directions.
   • Calculate the score for the current subarray as min(nums[left], nums[left+1], ..., nums[right]) * (right - left + 1).
   • Update maxScore if the score of the current subarray is greater than maxScore.
4. Return the maxScore.

Time Complexity

The time complexity of this algorithm is O(n), where n is the length of the input array nums.

Space Complexity

The space complexity of this algorithm is O(1) as we are using a constant amount of extra space.

class Solution {
    public int maximumScore(int[] nums, int k) {
        int n = nums.length;
        int maxScore = 0;
        
        for (int i = k, j = k, minVal = nums[k];; minVal = Math.min(minVal, Math.min(nums[i], nums[j]))) {
            while (i > 0 && nums[i - 1] >= minVal) i--;
            while (j < n - 1 && nums[j + 1] >= minVal) j++;
            
            maxScore = Math.max(maxScore, minVal * (j - i + 1));
            
            if (i == 0 && j == n - 1) break;
            if (i == 0) j++;
            else if (j == n - 1) i--;
            else if (nums[i - 1] > nums[j + 1]) i--;
            else j++;
        }
        
        return maxScore;
    }
}