[LeetCode] 1793. Maximum Score of a Good Subarray

https://leetcode.com/problems/maximum-score-of-a-good-subarray/description/

Maximum Score of a Good Subarray - LeetCode

LeetCode - 1793. Maximum Score of a Good Subarray

문제 유형 : 투 포인터

문제 난이도 : Hard

 

문제

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.

 

당신은 0-indexed의 정수 배열 nums와 정수 k를 받습니다.

 

부분배열(i, j)의 점수는 (부분배열의 최솟값) * (j-i+1)입니다.

 

좋은 부분배열은 i <= k <= j를 만족합니다.

 

좋은 부분배열의 가장 큰 점수를 구하시오.

 

 

풀이

투 포인터로 해결할 수 있습니다. 부분배열의 왼쪽 포인터 left, 오른쪽 포인터 right을 만들어줍니다. 둘 다 처음에는 k에서 시작합니다.

최소값도 초기화해줍니다. nums[k]를 처음의 최소값으로 합니다.

 

그렇게 점수를 구해보면서 가장 큰 값을 갱신해주면 되는데, left와 right의 증감 조건을 다음과 같습니다:

    1. left가 0보다 큰 경우(왼쪽으로 더 뻗을 수 있는 경우)

         a. 우선, right이 n-1보다 작은지 확인합니다(오른쪽으로 더 뻗을 수 있는지). 오른쪽으로 더 뻗을 수 없다면, left를 왼쪽으로 보내고, 최소값을 갱신합니다.(기존 최소값과 nums[--left]와 비교)

             ㄱ. nums[left-1]이 nums[right+1]보다 더 크거나 같으면 left를 왼쪽으로 보내고, 최소값을 갱신합니다.

             ㄴ. 아니라면, right을 오른쪽으로 보내고, 최소값을 갱신합니다.

    2. left가 더 왼쪽으로 뻗을 수 없는 경우

         a. right가 더 오른쪽으로 뻗을 수 있는지 확인합니다. 

             ㄱ. 더 뻗을 수 있다면, right을 오른쪽으로 보내고, 최소값을 갱신합니다.

             ㄴ. 더 뻗을 수 없다면, left와 right 둘 다 양 끝으로 와서 탐색이 불가능하므로 반복문을 끝냅니다.

 

최대 스코어를 반환합니다.

 

코드

C++

class Solution{
public:
    int maximumScore(vector<int> &nums, int k){
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        const int n = nums.size();
        int left = k;
        int right = k;
        int minNum = nums[k];
        int maxScore = INT_MIN;
        while (true){
            // update maxScore..
            int score = (right - left + 1) * minNum;
            maxScore = max(maxScore, score);

            if (left > 0){
                if (right < n-1){
                    if (nums[left - 1] >= nums[right + 1]){
                        left--;
                        minNum = min(minNum, nums[left]);
                    }
                    else{
                        right++;
                        minNum = min(minNum, nums[right]);
                    }
                }
                else{
                    left--;
                    minNum = min(minNum, nums[left]);
                }
            }
            else{
                if (right < n-1){
                    right++;
                    minNum = min(minNum, nums[right]);
                }
                //end: left == 0 && right == n-1
                else break;
            }
        }

        return maxScore;
    }
};