LeetCode_maximum-points-you-can-obtain-from-cards (Java)

1538. Maximum Points You Can Obtain from Cards

Medium

---

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.

 

Constraints:

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

문제 풀이

누적합으로 풀이했다. 한 쪽에서 연속으로 뽑을 수 있고 왼쪽과 오른쪽만 선택 가능하므로 양쪽에서 각각 연속으로 몇개를 뽑는가가 중요하다. 순서는 상관없고 개수가 중요하다.

코드

import java.util.*;

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int sum=0;
        for(int i=0; i<n; i++){
            sum += cardPoints[i];
        }

        if(k >=n) return sum;

        int[] LtoR_PrefixSum = new int[n];
        int[] RtoL_PrefixSum = new int[n];

        LtoR_PrefixSum[0] = cardPoints[0];
        for(int i=1; i<n; i++){
            LtoR_PrefixSum[i] = LtoR_PrefixSum[i-1] + cardPoints[i];
        }

        RtoL_PrefixSum[n-1] = cardPoints[n-1];
        for(int i=n-2; i>=0; i--){
            RtoL_PrefixSum[i] = RtoL_PrefixSum[i+1] + cardPoints[i];
        }

        System.out.println(Arrays.toString(LtoR_PrefixSum));
        System.out.println(Arrays.toString(RtoL_PrefixSum));

        int left = k-1;
        int right = n;

        int res = Math.max(LtoR_PrefixSum[k-1], RtoL_PrefixSum[n-k]);
        for(int i = 1; i<= k-1; i++){
            res = Math.max(res, LtoR_PrefixSum[left - i] + RtoL_PrefixSum[right - i]);
        }
        return res;
    }
}