1793. Maximum Score of a Good Subarray

• 두 개의 포인터 s, e를 사용하여 현재의 최소값 minVal이 유지되는 범위를 찾아서 결과값을 계산한다.

• 기본적인 아이디어는 비슷하게 접근했지만 범위를 확장하는 방식을 불필요하게 어렵게 구현했던 것이 시간 초과로 이어졌다.
• 정확하게 현재의 최소값 minVal이 유지되는 범위를 찾고, 다음 iteration에서 현재 범위의 앞에서 -1, 뒤에서 +1 위치 각각을 따로 탐색하는 방식으로 구현하였다.
• 이렇게 하면 경우의 수가 기하급수적으로 증가할 수 있기 때문에 문제가 된다.

• 범위를 점차 확장하되 현재 범위의 앞에서 -1, 뒤에서 +1 위치의 숫자 중 큰 값을 기준으로 범위를 확장한다.
• 둘 중 큰 값을 선택할 수록 현재 최소값 보다 크거나 같은 값을 선택할 확률이 높기 때문이다.

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int s = k, e = k, N = nums.size();
        int minVal = nums[k];
        int result = nums[k];
        while (s > 0 || e < N - 1) {
            if (s == 0 || (e < N - 1 && nums[e + 1] > nums[s - 1]))
                ++e;
            else
                --s;
            minVal = min(minVal, min(nums[s], nums[e]));
            result = max(result, minVal * (e - s + 1));
        }
        return result;
    }
};