Maximum Score of a Good Subarray - Practice Coding Problems

Maximum Score of a Good Subarray - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,4,3,7,4,5], k = 3

› Output: 15

💡 Note: The optimal subarray is [3,7,4] from index 2 to 4. Minimum value is 3, length is 3, so score = 3 × 3 = 9. Actually, [7] gives score 7×1=7, but [3,7] gives 3×2=6, [3,7,4] gives 3×3=9, [7,4] gives 4×2=8, [7,4,5] gives 4×3=12, [3,7,4,5] gives 3×4=12, [4,3,7,4,5] gives 3×5=15.

Example 2 — Single Element Best

$ Input: nums = [5,5,4,5,4,1,1,1], k = 0

› Output: 20

💡 Note: k=0, so we must include nums[0]=5. The best subarray is [5,5,4,5] from index 0 to 3, with minimum 4 and length 4, giving score = 4 × 4 = 16. Wait, [5,5] gives 5×2=10, [5,5,4,5] gives 4×4=16, [5,5,4,5,4] gives 4×5=20.

Example 3 — Edge Position

$ Input: nums = [1,4,3,7,4,5], k = 5

› Output: 15

💡 Note: k=5 (last position), nums[5]=5. We expand left: [5] score=5, [4,5] score=8, [7,4,5] score=12, [3,7,4,5] score=12, [4,3,7,4,5] score=15, [1,4,3,7,4,5] score=6. Maximum is 15.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 2 × 10⁴
0 ≤ k < nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,4,3,7,4,5] with k=3

Process

Find subarray containing index 3 with max(min × length)

Output

Maximum score is 15 from subarray [1,4,3,7,4]

Key Takeaway

🎯 Key Insight: Use greedy two-pointer expansion from k toward higher values to maximize score efficiently

Asked in

A Amazon 25 G Google 20 F Facebook 15

The key insight is to use a greedy two-pointer approach starting from index k and always expanding toward the side with the higher value. This maximizes the potential score while maintaining the minimum constraint. Best approach is Two Pointers with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers - Expand from Center	O(n)	O(1)	Start at k and greedily expand left or right to maximize score
Brute Force - Check All Subarrays	O(n³)	O(1)	Check every possible subarray that includes index k

Two Pointers - Expand from Center — Algorithm Steps

Step 1: Initialize left and right pointers at k, with initial score nums[k]
Step 2: While we can expand left or right, choose the side with higher value
Step 3: Update minimum value and calculate new score after each expansion
Step 4: Track maximum score throughout the process

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with single element at k

Expand

Choose side with higher value to expand

Update

Calculate score and track maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int k) {
    int left = k, right = k;
    int minVal = nums[k];
    int maxScore = nums[k];
    
    while (left > 0 || right < numsSize - 1) {
        // Choose which side to expand
        int leftVal = left > 0 ? nums[left - 1] : -1;
        int rightVal = right < numsSize - 1 ? nums[right + 1] : -1;
        
        // Expand toward the side with higher value
        if (leftVal > rightVal) {
            left--;
            if (nums[left] < minVal) {
                minVal = nums[left];
            }
        } else {
            right++;
            if (nums[right] < minVal) {
                minVal = nums[right];
            }
        }
        
        // Calculate new score and update maximum
        int score = minVal * (right - left + 1);
        if (score > maxScore) {
            maxScore = score;
        }
    }
    
    return maxScore;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element is visited at most once during expansion

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for pointers and tracking

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers - Expand from Center — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler