LeetCode - Maximum Points You Can Obtain from Cards

문제 설명

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

입출력 예시

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

제약사항

1 <= cardPoints.length <= 105
1 <= cardPoints[i] <= 104
1 <= k <= cardPoints.length

Solution

[전략]
1. 오른쪽에서부터 k개를 선택한 합계를 구한 후,
2. 왼쪽에서부터 하나씩 선택하고,
오른쪽에서는 원소를 하나씩 배제해보면서 가능한 케이스별 최대합을 비교해본다

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int cardPointsLen = cardPoints.length;
        
        int rightSum=cardPoints[cardPointsLen-1];

        // 오른쪽에서 k를 선택한 합을 구함
        for (int j = cardPointsLen - 2; j >= cardPoints.length - k; j--) {
            rightSum = rightSum + cardPoints[j];
        }
        if (cardPointsLen == k) {
            return rightSum;
        }

        int maxSum=rightSum;
        
        // 왼쪽에서 한개씩 선택을 늘여가고, 오른쪽에선 한개씩 선택을 빼면서 최대 합을 구함
        int leftSum = 0;
        for (int i = 0; i < k; i++) {
            leftSum = leftSum + cardPoints[i];
            rightSum = rightSum - cardPoints[cardPoints.length - k + i];
            int total = leftSum + rightSum;
            if (total > maxSum) {
                maxSum = total;
            }
        }
        return maxSum;
    }
}