LeetCode 1793: Maximum Score of a Good Subarray Solution

Master LeetCode problem 1793 (Maximum Score of a Good Subarray), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1793. Maximum Score of a Good Subarray

Hard

Array Two Pointers Binary Search Stack Monotonic Stack

Problem Explanation

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

Initialize a variable n to store the length of the input array nums.
Initialize a variable maxScore to keep track of the maximum score found so far.
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.
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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1793 (Maximum Score of a Good Subarray)?

This page provides optimized solutions for LeetCode problem 1793 (Maximum Score of a Good Subarray) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1793 (Maximum Score of a Good Subarray)?

The time complexity for LeetCode 1793 (Maximum Score of a Good Subarray) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1793 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1793 in Java, C++, or Python.

Back to LeetCode Solutions