Maximum Score of a Good Subarray

hard array two pointers

Problem

You are given an array nums and an index k. A subarray spanning indices i to j is good when it contains k, that is i ≤ k ≤ j. The score of such a subarray equals the smallest value inside it multiplied by its length: min(nums[i..j]) × (j − i + 1). Return the largest score over every good subarray.

Inputnums = [1, 4, 3, 7, 4, 5], k = 3

Output15

The subarray [4, 3, 7, 4, 5] (indices 1..5) has minimum 3 and length 5, so its score is 3 × 5 = 15, which is the best.

nums (comma-separated)

def maximumScore(nums, k):
    n = len(nums)
    i = j = k
    mn = nums[k]
    ans = mn
    while i > 0 or j < n - 1:
        left = nums[i - 1] if i > 0 else -1
        right = nums[j + 1] if j < n - 1 else -1
        if left < right:
            j += 1
            mn = min(mn, nums[j])
        else:
            i -= 1
            mn = min(mn, nums[i])
        ans = max(ans, mn * (j - i + 1))
    return ans

function maximumScore(nums, k) {
  const n = nums.length;
  let i = k, j = k;
  let mn = nums[k];
  let ans = mn;
  while (i > 0 || j < n - 1) {
    const left = i > 0 ? nums[i - 1] : -1;
    const right = j < n - 1 ? nums[j + 1] : -1;
    if (left < right) {
      j += 1;
      mn = Math.min(mn, nums[j]);
    } else {
      i -= 1;
      mn = Math.min(mn, nums[i]);
    }
    ans = Math.max(ans, mn * (j - i + 1));
  }
  return ans;
}

class Solution {
    public int maximumScore(int[] nums, int k) {
        int n = nums.length;
        int i = k, j = k;
        int mn = nums[k];
        int ans = mn;
        while (i > 0 || j < n - 1) {
            int left = i > 0 ? nums[i - 1] : -1;
            int right = j < n - 1 ? nums[j + 1] : -1;
            if (left < right) {
                j += 1;
                mn = Math.min(mn, nums[j]);
            } else {
                i -= 1;
                mn = Math.min(mn, nums[i]);
            }
            ans = Math.max(ans, mn * (j - i + 1));
        }
        return ans;
    }
}

int maximumScore(vector<int>& nums, int k) {
    int n = (int)nums.size();
    int i = k, j = k;
    int mn = nums[k];
    int ans = mn;
    while (i > 0 || j < n - 1) {
        int left = i > 0 ? nums[i - 1] : -1;
        int right = j < n - 1 ? nums[j + 1] : -1;
        if (left < right) {
            j += 1;
            mn = min(mn, nums[j]);
        } else {
            i -= 1;
            mn = min(mn, nums[i]);
        }
        ans = max(ans, mn * (j - i + 1));
    }
    return ans;
}

Explanation

Every good subarray must cover index k, so we can picture two pointers i and j that both start sitting on k. The subarray is whatever lies between them, and the only ways to make it bigger are to push i one step left or j one step right.

The score is min × length. Growing the window always increases the length by one, but it can only lower the minimum, never raise it. So the question at each step is simply: which side should we expand?

The greedy answer is to step toward the larger neighbor. Whichever value we absorb might become the new minimum, so absorbing the bigger of the two keeps the running minimum as high as possible for as long as possible. We compare nums[i-1] with nums[j+1] (treating a missing side as −1 so we are forced to use the side that still has room) and move toward the higher one.

After each move we refresh mn = min(mn, absorbed value) and record a candidate score mn × (j - i + 1). The best candidate seen across the whole expansion is the answer.

Walking the example nums = [1, 4, 3, 7, 4, 5], k = 3: we start on 7, then repeatedly step toward the taller neighbor. The window grows to [4, 3, 7, 4, 5] where the minimum is 3 and length is 5, giving 3 × 5 = 15 — the maximum.

Time: O(n) Space: O(1)