C ++中可被三除的最大和

假设我们有一个整数的数组，我们需要找到给定数组的元素的最大可能和，以使其可以被三整除。因此，如果输入类似于[3,6,5,1,8]，则输出将为18，因为子数组为[3,6,1,8]，总和为18，可以被3整除。

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

• n：= nums数组的大小

• 创建一个大小为（n + 1）x 3的2d数组dp

• 设置dp [0，0]：= 0，dp [0,1]：= -inf，dp [0,2]：= inf

• 当i在1到n的范围内时；

• k：=（x + j）mod 3

• dp [i，k]：= dp [i，k]和dp [i – 1，j] + x的最大值

• x：= nums [i-1]

• 对于介于0到2之间的j，dp [i，j]：= dp [i – 1，j]

• 对于0到2范围内的j

• 返回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