# Maximum Score of a Good Subarray
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-score-of-a-good-subarray)
Canonical: https://scaleengineer.com/dsa/problems/maximum-score-of-a-good-subarray
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Stack, Monotonic Stack
---
## Problem
You are given an array of integers `nums` **(0-indexed)** and an integer `k`.

The **score** of a subarray `(i, j)` is defined as `min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1)`. A **good** subarray is a subarray where `i <= k <= j`.

Return _the maximum possible **score** of a **good** subarray._

**Example 1:**

**Input:** nums = [1,4,3,7,4,5], k = 3
**Output:** 15
**Explanation:** The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15. 

**Example 2:**

**Input:** nums = [5,5,4,5,4,1,1,1], k = 0
**Output:** 20
**Explanation:** The optimal subarray is (0, 4) with a score of min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 2 * 104`
* `0 <= k < nums.length`

# Approaches
## Brute Force over Good Subarrays
The most straightforward approach is to check every possible "good" subarray. A subarray `(i, j)` is considered good if it contains the index `k`, which means `i <= k <= j`. We can use nested loops to generate all such subarrays, calculate their scores, and keep track of the maximum score.
**Time:** O(N^2), where N is the length of the `nums` array. The outer loop runs `k+1` times, and the inner loops combined run in `O(N)` time for each `i`, leading to a total complexity of `O(k*N)`, which is `O(N^2)` in the worst case. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** It's relatively simple to understand and implement.; It correctly explores all possibilities and guarantees finding the optimal solution.
**Cons:** This approach is too slow for the given constraints (`N` up to 10^5) and will likely result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
This method involves a brute-force check of all valid subarrays. We can set up two nested loops: the outer loop iterates through all possible start indices `i` from `0` to `k`, and the inner loop iterates through all possible end indices `j` from `k` to `n-1`.

A naive implementation would find the minimum of `nums[i...j]` in a third loop, leading to an `O(N^3)` complexity. We can optimize this to `O(N^2)` by noticing that for a fixed start `i`, as we expand the end `j`, the minimum of the subarray can be updated incrementally.

Here is the `O(N^2)` algorithm:
1.  Initialize `maxScore = 0`.
2.  Loop `i` from `0` to `k`.
3.  Initialize `min_i_to_k` by finding the minimum in `nums[i...k]`.
4.  Loop `j` from `k` to `n-1`.
5.  In this loop, update the overall minimum for `nums[i...j]` based on the previous minimum and `nums[j]`.
6.  Calculate the score for `(i, j)` and update `maxScore`.

```java
class Solution {
    public int maximumScore(int[] nums, int k) {
        int n = nums.length;
        int maxScore = 0;

        // Iterate through all possible start indices i <= k
        for (int i = 0; i <= k; i++) {
            int currentMin = nums[k];
            // Find minimum in the left part of the subarray [i, k]
            for (int p = k; p >= i; p--) {
                currentMin = Math.min(currentMin, nums[p]);
            }

            // Now expand to the right part [k, j]
            // The minimum from i to k is already computed in currentMin
            int minForSubarray = currentMin;
            for (int j = k; j < n; j++) {
                minForSubarray = Math.min(minForSubarray, nums[j]);
                int score = minForSubarray * (j - i + 1);
                maxScore = Math.max(maxScore, score);
            }
        }
        return maxScore;
    }
}
```
### Algorithm
*   Initialize `maxScore` to 0.
*   Iterate through all possible start indices `i` from `0` to `k`.
*   For each `i`, start an inner loop for all possible end indices `j` from `k` to `n-1`.
*   For each pair of `(i, j)`, we have a "good" subarray.
*   To calculate the score, find the minimum element `currentMin` in the subarray `nums[i...j]`.
*   Calculate the score as `currentMin * (j - i + 1)`.
*   Update `maxScore` with the maximum score found so far.
*   To avoid a third loop which would make the complexity `O(N^3)`, we can optimize finding the minimum. For a fixed `i`, as `j` increases, we can update the minimum in `O(1)` time.
*   The refined algorithm iterates `i` from `0` to `k`. For each `i`, it calculates the minimum from `i` to `k`, then extends to the right towards `n-1`, updating the minimum and score at each step.

## Greedy Two Pointers
A much more efficient solution uses a two-pointer, greedy approach. We start with the smallest possible good subarray, which is just the element at index `k`. We then expand this subarray one element at a time, either to the left or to the right. The greedy choice at each step is to expand in the direction of the larger element. This strategy aims to keep the minimum value of the subarray as high as possible for as long as possible, which helps in maximizing the score.
**Time:** O(N), where N is the length of the `nums` array. The pointers `i` and `j` start at `k` and together they traverse the rest of the array elements exactly once. · **Space:** O(1), as it only requires a few variables to keep track of the pointers and scores.
**Pros:** This approach is highly efficient, with a linear time complexity.; It uses constant extra space, making it very memory-efficient.; It is the optimal solution for this problem.
**Cons:** The greedy logic, while correct, might not be immediately obvious and can be harder to reason about than a simple brute-force approach.
### Explanation
We can think of this problem as finding an optimal balance between the minimum value of a subarray and its length. The two-pointer approach elegantly explores this trade-off.

We initialize pointers `i` and `j` to `k`. This represents the initial subarray `(k, k)`. We then iteratively expand this window `(i, j)`. At each step, we look at the elements just outside our current window, `nums[i-1]` and `nums[j+1]`. To maximize the score `min * length`, we want to increase the length while keeping `min` high. By expanding towards the larger of `nums[i-1]` and `nums[j+1]`, we make a greedy choice that is less likely to decrease our current minimum. This process continues until the window has expanded to cover all elements that could potentially form a better-scoring subarray.

```java
class Solution {
    public int maximumScore(int[] nums, int k) {
        int n = nums.length;
        int i = k, j = k;
        int maxScore = nums[k];
        int currentMin = nums[k];

        // Expand the window [i, j] until it can't be expanded further
        while (i > 0 || j < n - 1) {
            // Get the values of potential next elements, handle boundaries by using 0
            int leftVal = (i > 0) ? nums[i - 1] : 0;
            int rightVal = (j < n - 1) ? nums[j + 1] : 0;

            // Greedily expand towards the larger element
            if (leftVal > rightVal) {
                i--;
                currentMin = Math.min(currentMin, nums[i]);
            } else {
                j++;
                currentMin = Math.min(currentMin, nums[j]);
            }
            
            // Update the maximum score
            maxScore = Math.max(maxScore, currentMin * (j - i + 1));
        }

        return maxScore;
    }
}
```
### Algorithm
*   Initialize two pointers, `i` and `j`, at index `k`.
*   Initialize `maxScore` and `currentMin` with the value `nums[k]`.
*   Start a loop that continues as long as the subarray can be expanded (i.e., `i > 0` or `j < n-1`).
*   Inside the loop, decide which pointer to move. Compare the values at the neighbors `nums[i-1]` and `nums[j+1]` (handling boundary cases where a neighbor doesn't exist).
*   Greedily move the pointer that points towards the larger neighbor. This is done to keep the `currentMin` as high as possible, thus maximizing the score.
*   If `i` is at the start (`i=0`), you must move `j` right.
*   If `j` is at the end (`j=n-1`), you must move `i` left.
*   Otherwise, if `nums[i-1] > nums[j+1]`, move `i` left. Else, move `j` right.
*   After moving a pointer, update `currentMin` with the new element.
*   Calculate the score for the new subarray `(i, j)` as `currentMin * (j - i + 1)`.
*   Update `maxScore` if the new score is greater.
*   Return `maxScore` after the loop finishes.

# Solutions
### Java

```java
class Solution { public int maximumScore ( int [] nums , int k ) { int n = nums . length ; int [] left = new int [ n ]; int [] right = new int [ n ]; Arrays . fill ( left , - 1 ); Arrays . fill ( right , n ); Deque < Integer > stk = new ArrayDeque <>(); for ( int i = 0 ; i < n ; ++ i ) { int v = nums [ i ]; while (! stk . isEmpty () && nums [ stk . peek ()] >= v ) { stk . pop (); } if (! stk . isEmpty ()) { left [ i ] = stk . peek (); } stk . push ( i ); } stk . clear (); for ( int i = n - 1 ; i >= 0 ; -- i ) { int v = nums [ i ]; while (! stk . isEmpty () && nums [ stk . peek ()] > v ) { stk . pop (); } if (! stk . isEmpty ()) { right [ i ] = stk . peek (); } stk . push ( i ); } int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( left [ i ] + 1 <= k && k <= right [ i ] - 1 ) { ans = Math . max ( ans , nums [ i ] * ( right [ i ] - left [ i ] - 1 )); } } return ans ; } }
```

### CPP

```cpp
class Solution { public: int maximumScore ( vector < int >& nums , int k ) { int n = nums . size (); vector < int > left ( n , - 1 ); vector < int > right ( n , n ); stack < int > stk ; for ( int i = 0 ; i < n ; ++ i ) { int v = nums [ i ]; while ( ! stk . empty () && nums [ stk . top ()] >= v ) { stk . pop (); } if ( ! stk . empty ()) { left [ i ] = stk . top (); } stk . push ( i ); } stk = stack < int > (); for ( int i = n - 1 ; i >= 0 ; -- i ) { int v = nums [ i ]; while ( ! stk . empty () && nums [ stk . top ()] > v ) { stk . pop (); } if ( ! stk . empty ()) { right [ i ] = stk . top (); } stk . push ( i ); } int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( left [ i ] + 1 <= k && k <= right [ i ] - 1 ) { ans = max ( ans , nums [ i ] * ( right [ i ] - left [ i ] - 1 )); } } return ans ; } };
```

### Python

```python
class Solution : def maximumScore ( self , nums : List [ int ], k : int ) -> int : n = len ( nums ) left = [ - 1 ] * n right = [ n ] * n stk = [] for i , v in enumerate ( nums ): while stk and nums [ stk [ - 1 ]] >= v : stk . pop () if stk : left [ i ] = stk [ - 1 ] stk . append ( i ) stk = [] for i in range ( n - 1 , - 1 , - 1 ): v = nums [ i ] while stk and nums [ stk [ - 1 ]] > v : stk . pop () if stk : right [ i ] = stk [ - 1 ] stk . append ( i ) ans = 0 for i , v in enumerate ( nums ): if left [ i ] + 1 <= k <= right [ i ] - 1 : ans = max ( ans , v * ( right [ i ] - left [ i ] - 1 )) return ans
```