C++のカードから取得できる最大ポイント

複数のカードが一列に配置され、各カードにポイントが関連付けられており、これらのポイントがcardPointsと呼ばれる整数配列で指定されているとします。 1つのステップで、行の最初または最後から1枚のカードを取得できます。正確にk枚のカードを取る必要があります。最終的なスコアは、私たちが取ったカードのポイントの合計になります。したがって、整数配列cardPointsと整数kがある場合は、取得できる最大スコアを見つけます。

したがって、入力がcardPoints =[1,2,3,4,5,6,1]、k =3の場合、最初のステップの後、スコアは常に1になるため、出力は12になります。 、最初に右端のカードを選択すると、合計スコアが最大になります。最適な戦略は、右側の3枚のカードを取り、最終スコアを1 + 6 + 5=12にすることです。

これを解決するには、次の手順に従います-

• 2つの配列pre1とprev2を定義し、v

  で初期化します。

• ret：=0

• n：=vのサイズ

• 初期化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]を返す

• i：=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]

• 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