您可以从C ++卡中获得的最高积分

假设有几张卡片排成一行，每张卡片都有关联的点，这些点在称为cardPoints的整数数组中给出。第一步，我们可以从行的开头或结尾取出一张卡片。我们必须要拿k张卡。最终分数将是我们所取得的牌点的总和。因此，如果我们有整数数组cardPoints和整数k，则找到我们可以获得的最大分数。

因此，如果输入像cardPoints = [1,2,3,4,5,6,1]，k = 3，那么输出将为12，因为在初始步骤之后，我们的得分将始终为1。 ，请先选择最右边的卡片，以使总分最大化。最佳策略是拿右边的三张牌，最终得分为1 + 6 + 5 = 12。

为了解决这个问题，我们将遵循以下步骤-

• 定义两个数组pre1和prev2并使用v对其进行初始化

• ret：= 0

• n：= v的大小

• 对于初始化i：= 1，当i <n时，更新（将i增加1），-

• 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]

• i：= k-1

• ret：= pre1 [i]

• （将i减1）

• j：= n-1

• 当我> = 0时，-

• ret：= ret的最大值和（pre1 [i] + pre2 [j]）

• 将i和j减1

• ret：= ret和pre2 [n-k]的最大值

• 返回ret

例 

让我们看下面的实现以更好地理解-

#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}

输出结果

12