1793. Good Subarray Score

Maximum Score of a Good Subarray

From this problem's definition of a good subarray's boundaries:

Left Boundary $\leq k \leq$ Right Boundary,

we can see that every candidate subarray must contain $nums[k]$.

Since $nums[k]$ Is A Must

Why not let $nums[k]$ be the center of our greedy search?

Set up two pointers: leftIdx and rightIdx.

One scans from $k$ to left, the other scans from $k$ to right.

Each step goes into one of three cases:

I. Both leftIdx and rightIdx are in bounds.

Compare nums[leftIdx] and nums[rightIdx].

The bigger one becomes the new member to extend current subarray.

Why pick the bigger one: subarray score = subarray minimum * subarray length.

A bigger new member is more likely to maintain the subarray minimum,

or at least minimizes the drop from minimum.

II. leftIdx is out of bounds. Only rightIdx can increment.

III. rightIdx is out of bounds. Only leftIdx can decrement.

Such a design covers all subarrays having $nums[k]$.

After each step, compute current subarray's score,

comparing it with maxScore and update when necessary.

Time complexity is $O(n)$. Each element is visited exactly once.

Space complexity is $O(1)$. We just need two pointers,

current subarray minimum & score, and historical max score. 5 variables after all.

BTW, this greedy two pointers approach was later submitted as a pull request by me,

and was merged into LeetCode Wiki, reducing space complexity from $O(n)$ to $O(1)$.

C++

#include <vector>
using namespace std;

int findMaxScore(vector<int>& nums, int k) // LeetCode Q.1793.
{
    int maxScore = nums[k], minNum = nums[k]; // Base case.

    int leftIdx = k, rightIdx = k;

    while (0 < leftIdx || rightIdx < nums.size() - 1) {
        if (leftIdx == 0) { // Can only go right.
            rightIdx++;
            minNum = min(minNum, nums[rightIdx]);
        }

        else if (rightIdx == nums.size() - 1) { // Can only go left.
            leftIdx--;
            minNum = min(minNum, nums[leftIdx]);
        }

        else { // Can go bidirectional.
            if (nums[leftIdx - 1] >= nums[rightIdx + 1]) {
                leftIdx--;
                minNum = min(minNum, nums[leftIdx]);
            }

            else {
                rightIdx++;
                minNum = min(minNum, nums[rightIdx]);
            }
        }

        int score = minNum * (rightIdx + 1 - leftIdx);
        maxScore = max(maxScore, score);
    }

    return maxScore;
}

Python

def find_max_score(nums: list[int], k: int) -> int:  # LeetCode Q.1793.
    max_score = nums[k]  # Base case.
    min_num = nums[k]

    left_idx, right_idx = k, k

    while 0 < left_idx or right_idx < len(nums) - 1:
        if left_idx == 0:  # Can only go right.
            right_idx += 1
            min_num = min(min_num, nums[right_idx])
        
        elif right_idx == len(nums) - 1:  # Can only go left.
            left_idx -= 1
            min_num = min(min_num, nums[left_idx])

        else:  # Can go bidirectional.
            if nums[left_idx - 1] >= nums[right_idx + 1]:
                left_idx -= 1
                min_num = min(min_num, nums[left_idx])

            else:
                right_idx += 1
                min_num = min(min_num, nums[right_idx])

        score = min_num * (right_idx + 1 - left_idx)
        max_score = max(max_score, score)

    return max_score