C++で3で割り切れる最大の合計

整数の配列numsがあるとすると、3で割り切れるような、与えられた配列の要素の可能な最大の合計を見つける必要があります。したがって、入力が[3,6,5,1,8]の場合、サブ配列は[3,6,1,8]であり、合計は18であるため、出力は18になり、3で割り切れます。 。

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

• n：=nums配列のサイズ
• サイズ（n + 1）x3の2次元配列dpを1つ作成します
• set dp [0、0]：=0、dp [0,1]：=-inf、dp [0,2]：=inf
• 1からnの範囲のiの場合;
  • x：=nums [i-1]
  • 0〜2の範囲のjの場合、dp [i、j]：=dp [i – 1、j]
  • 0〜2の範囲のjの場合
    • k：=（x + j）mod 3
    • dp [i、k]：=dp [i、k]およびdp [i – 1、j]+xの最大値
• return dp [n、0]

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxSumDivThree(vector<int>& nums) {
      int n = nums.size();
      int dp[n+1][3];
      dp[0][0] = 0;
      dp[0][1] = INT_MIN;
      dp[0][2] = INT_MIN;
      for(int i = 1; i <= n; i++){
         int x = nums[i-1];
         for(int j = 0; j < 3; j++)dp[i][j] = dp[i-1][j];
         for(int j = 0; j < 3; j++){
            int k = (x + j) % 3;
            dp[i][k] = max(dp[i][k],dp[i-1][j] + x);
         }
      }
      return dp[n][0];
   }
};
main(){
   vector<int> v = {3,6,5,1,8};
   Solution ob;
   cout << (ob.maxSumDivThree(v));
}

入力

[3,6,5,1,8]

出力

18