Problem statement

You are given an integer array nums and an index k. The score of a subarray nums[i..j] is min(nums[i..j]) * (j - i + 1) — its smallest element times its length.

A subarray is good when it contains index k, that is i <= k <= j. Return the maximum score over all good subarrays.

Example 1

Input: nums = [2,6,4,8,3], k = 2
Output: 12
Explanation: `[6,4,8]` scores 4 × 3 = 12, and so does `[6,4,8,3]` with 3 × 4.

Example 2

Input: nums = [7,1,7,7,7], k = 3
Output: 21
Explanation: `[7,7,7]` (indices 2–4) avoids the 1.

Example 3

Input: nums = [5], k = 0
Output: 5

Constraints

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 2 * 10^4
• 0 <= k < nums.length

Hints for Maximum Score of a Good Subarray

1. Hint 1

   Every good subarray grows outward from index k. Think of starting with [k, k] and widening it one element at a time.

2. Hint 2

   When you widen, the minimum can only stay the same or drop. Which side should you take to keep it as high as possible?

3. Hint 3

   Always extend toward the larger of the two neighbours (nums[i - 1] vs nums[j + 1]), update the running minimum, and record min × length after every step.

How to solve Maximum Score of a Good Subarray

Grow the window from [k, k] greedily, always swallowing the larger neighbour. For every possible minimum value this reaches the widest good window with that minimum, so the best score is seen along the way.

Approach

1. Set i = j = k, cur = nums[k], best = cur.
2. While the window can still grow: if the left end is at 0, or the right neighbour nums[j + 1] is larger than the left neighbour nums[i - 1], extend right; otherwise extend left.
3. Update cur to the minimum of the window and best = max(best, cur × (j - i + 1)).
4. Return best once the window covers the whole array.

Why it works

Fix a threshold v. The widest good window whose elements are all >= v is the maximal run around k of elements >= v. The greedy never steps past an element smaller than v while a neighbour >= v is still available on the other side, so at some moment its window equals that maximal run — and at that moment its score is at least v times the run's length. Taking v as the minimum of the optimal subarray shows the greedy records a score at least as large as the optimum.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Checking only subarrays that start or end at k misses windows spreading both ways.
• Handle the borders: once one side is exhausted, only the other side can grow.
• The product reaches 2 · 10^9 — near the top of int32, so compute it with care in languages that overflow silently.

Reference solution

Python

from typing import List

def maximumScore(nums: List[int], k: int) -> int:
    n = len(nums)
    i = j = k
    cur = nums[k]
    best = cur
    while i > 0 or j < n - 1:
        if i == 0 or (j < n - 1 and nums[j + 1] > nums[i - 1]):
            j += 1
            cur = min(cur, nums[j])
        else:
            i -= 1
            cur = min(cur, nums[i])
        best = max(best, cur * (j - i + 1))
    return best

Java

public static int maximumScore(int[] nums, int k) {
    int n = nums.length;
    int i = k, j = k;
    int cur = nums[k];
    long best = cur;
    while (i > 0 || j < n - 1) {
        if (i == 0 || (j < n - 1 && nums[j + 1] > nums[i - 1])) {
            j++;
            cur = Math.min(cur, nums[j]);
        } else {
            i--;
            cur = Math.min(cur, nums[i]);
        }
        best = Math.max(best, (long) cur * (j - i + 1));
    }
    return (int) best;
}

C++

int maximumScore(vector<int>& nums, int k) {
    int n = nums.size();
    int i = k, j = k;
    int cur = nums[k];
    long long best = cur;
    while (i > 0 || j < n - 1) {
        if (i == 0 || (j < n - 1 && nums[j + 1] > nums[i - 1])) {
            j++;
            cur = min(cur, nums[j]);
        } else {
            i--;
            cur = min(cur, nums[i]);
        }
        best = max(best, (long long)cur * (j - i + 1));
    }
    return (int)best;
}

JavaScript

var maximumScore = function(nums, k) {
    var n = nums.length;
    var i = k, j = k;
    var cur = nums[k], best = cur;
    while (i > 0 || j < n - 1) {
        if (i === 0 || (j < n - 1 && nums[j + 1] > nums[i - 1])) {
            j++;
            cur = Math.min(cur, nums[j]);
        } else {
            i--;
            cur = Math.min(cur, nums[i]);
        }
        best = Math.max(best, cur * (j - i + 1));
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard