C++で3で割り切れる最大の合計を求める方法

問題の概要

整数の配列 nums が与えられたとき、配列の要素を選んで合計が3で割り切れるようにする場合の、最大の合計値を求める問題を考えます。例えば、入力が [3,6,5,1,8] の場合、出力は 18 になります。これは、要素 5 を除いた [3,6,1,8] を選んだときの合計が 18 となり、3で割り切れるためです。

解決のアプローチ

この問題は動的計画法(DP)を用いて効率的に解くことができます。dp[i][j] を「最初の i 個の要素の中から選んだ要素の合計を3で割った余りが j となるときの最大合計」と定義します。

具体的な手順は以下の通りです。

• n を配列 nums のサイズとします
• (n + 1) × 3 のサイズの2次元配列 dp を作成します
• dp[0][0] := 0、dp[0][1] := -inf、dp[0][2] := -inf と初期化します
• i を 1 から n まで繰り返します
  • x := nums[i - 1] とします
  • j が 0 から 2 の範囲で、dp[i][j] := dp[i - 1][j] とします
  • j が 0 から 2 の範囲で以下を繰り返します
    • k := (x + j) mod 3
    • dp[i][k] := max(dp[i][k], dp[i - 1][j] + x)
• 最後に 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

このアルゴリズムの計算量は O(n) であり、配列の各要素を一度ずつ処理するだけで答えが求まります。余りが 0、1、2 の3状態のみを管理すればよいため、メモリ効率も非常に良いのが特徴です。