[C] LeetCode 1793. Maximum Score of a Good Subarray

 

문제

번역

0-index 를 사용하는 정수 배열 nums가 주어진다.

부분 배열 \((i, j)\)의 score는 \(min(subarray) * (j-i+1)\) 로 정의된다.

좋은 부분배열은 k가 i 이상 j 이하일때 이다.

좋은 부분배열의 점수의 최대값을 반환해라.

접근 방법 및 소스 코드

일단 부분 배열에 k가 반드시 들어가야 하니 k부터 시작하는게 좋을 것이다.

k를 기준으로 왼쪽과 오른쪽으로 한칸씩 늘려가면서 현재 최대 점수와 비교하면서 최대점수를 늘리는지 줄이는지 찾아야 한다.

왼쪽으로 가는것과 오른쪽으로 가는것을 비교해서 더 큰 값을 갖는 쪽으로 일단 늘려본다.

늘렸을때 점수가 지금 점수보다 높다면 업데이트를 한다.

 

이러한 방식으로 양쪽 끝까지 다 탐색해봐야 한다.

 

int maximumScore(int* nums, int numsSize, int k) {
    int mx=nums[k], l=k, r=k, min = nums[k];
    while( l > 0 || r < numsSize-1) {
        if (l == 0) {
            r++;
        } else if (r == numsSize - 1) {
            l--;
        } else if (nums[l - 1] > nums[r + 1]) {
            l--;
        } else {
            r++;
        }
        if (nums[l] < min) min = nums[l];
        if (nums[r] < min) min = nums[r];
        int score = min * (r - l + 1);
        if (score > mx) mx = score;
    }
    return mx;
}

 

 

이런 결과가 나왔다.