C++의 카드에서 얻을 수 있는 최대 점수

<시간/>

여러 개의 카드가 한 행에 배열되어 있고 각 카드에 연결된 포인트가 있고 이러한 포인트가 cardPoints라는 정수 배열로 제공된다고 가정합니다. 한 단계에서 행의 시작이나 끝에서 카드 한 장을 가져올 수 있습니다. 정확히 k개의 카드를 가져와야 합니다. 최종 점수는 우리가 가져간 카드의 점수의 합이 될 것입니다. 따라서 정수 배열 cardPoints와 정수 k가 있는 경우 얻을 수 있는 최대 점수를 찾으십시오.

따라서 입력이 cardPoints =[1,2,3,4,5,6,1], k =3과 같으면 초기 단계 이후의 점수는 항상 1이므로 출력은 12가 됩니다. 이제 , 가장 오른쪽에 있는 카드를 먼저 선택하면 총 점수가 최대화됩니다. 최적의 전략은 오른쪽에 있는 세 장의 카드를 가져와서 1 + 6 + 5 =12의 최종 점수를 주는 것입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

두 개의 배열 pre1 및 prev2를 정의하고 v
로 초기화합니다.
렛 :=0
n :=v의 크기
initialize i :=1의 경우, i
- pre1[i] :=pre1[i] + pre1[i - 1]
초기화 i :=n - 2의 경우 i>=0일 때 업데이트(i 1만큼 감소), −
- pre2[i] :=pre2[i] + pre2[i + 1]
k>=n이면 -
- 반환 pre1[n - 1]
나는 :=k - 1
ret :=pre1[i]
(i를 1 감소)
j :=n - 1
i>=0인 동안 −
- ret :=ret의 최대값 및 (pre1[i] + pre2[j])
- i와 j를 1만큼 감소
ret :=ret 및 pre2의 최대값[n - k]
리턴 렛

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int maxScore(vector<int>& v, int k) {
      vector<int> pre1(v.begin(), v.end());
      vector<int> pre2(v.begin(), v.end());
      int ret = 0;
      int n = v.size();
      for (int i = 1; i < n; i++) {
         pre1[i] += pre1[i - 1];
      }
      for (int i = n - 2; i >= 0; i--) {
         pre2[i] += pre2[i + 1];
      }
      if (k >= n) {
         return pre1[n - 1];
      }
      int i = k - 1;
      ret = pre1[i];
      i--;
      int j = n - 1;
      while (i >= 0) {
         ret = max(ret, pre1[i] + pre2[j]);
         i--;
         j--;
      }
      ret = max(ret, pre2[n - k]);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5,6,1};
   cout << (ob.maxScore(v, 3));
}

입력

{1,2,3,4,5,6,1}