C++で合計が最大となるk個の重複しない部分リストの和を求めるプログラム

問題概要

数値のリスト nums と整数 k が与えられたとき、互いに重なり合わない空でない部分リストをちょうど k 個選び、それらの合計値の総和が最大となるようにします。なお、k は nums の要素数以下であると仮定して構いません。

たとえば、入力が nums = [11, -1, 2, 1, 6, -24, 11, -9, 6]、k = 3 である場合、出力は 36 になります。これは、部分リストとして [11, -1, 2, 1, 6]、[11]、[6] を選ぶと、その合計はそれぞれ 19、11、6 となり、総和が 19 + 11 + 6 = 36 になるためです。

アルゴリズムの考え方

この問題は動的計画法（DP）を用いることで効率的に解くことができます。ポイントは、次の2つの状態配列を管理することです。

• hi[i]: これまでに確定した部分リストの個数が i 個のときの、合計の最大値
• open[i]: i 個目の部分リストが「開いたまま」（直前の要素まで連続して含んでいる）状態における合計の最大値

各要素 num を処理する際には、次の2つの選択肢を比較します。

1. 既存の部分リストを延長する: open[i] + num
2. 新しい部分リストを開始する: hi[i - 1] + num

具体的な手順

• n := nums のサイズとする
• n が 0、または k が 0 の場合は 0 を返す
• サイズ k + 1 の配列 hi と open を用意し、すべて -inf（INT_MIN）で初期化する
• hi[0] := 0 とする
• nums の各要素 num について、以下を繰り返す
  • サイズ k + 1 の配列 nopen を -inf で初期化する
  • i を 1 から k まで増やしながら、次を実行する
    • open[i] > -inf ならば、nopen[i] := open[i] + num（既存の部分リストを延長）
    • hi[i - 1] > -inf ならば、nopen[i] := max(nopen[i], hi[i - 1] + num)（新しい部分リストを開始）
  • open := move(nopen)
  • i を 1 から k まで増やしながら、hi[i] := max(hi[i], open[i]) を実行する
• 最後に hi[k] を返す

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& nums, int k) {
   int n = nums.size();
   if (n == 0 || k == 0)
      return 0;
   vector<int> hi(k + 1, INT_MIN), open(k + 1, INT_MIN);
   hi[0] = 0;
   for (int num : nums) {
      vector<int> nopen(k + 1, INT_MIN);
      for (int i = 1; i <= k; ++i) {
         if (open[i] > INT_MIN)
            nopen[i] = open[i] + num;
         if (hi[i - 1] > INT_MIN)
            nopen[i] = max(nopen[i], hi[i - 1] + num);
      }
      open = move(nopen);
      for (int i = 1; i <= k; ++i)
      hi[i] = max(hi[i], open[i]);
   }
   return hi[k];
}
int main(){
   vector<int> v = {11, -1, 2, 1, 6, -24, 11, -9, 6};
   int k = 3;
   cout << solve(v, 3);
}

入力

{11, -1, 2, 1, 6, -24, 11, -9, 6}, 3

出力

36

計算量について

このアルゴリズムの時間計算量は O(n × k)、空間計算量は O(k) です。各要素ごとに k 個の状態を更新していくだけなので、入力サイズが大きくなっても効率的に動作します。また、INT_MIN を「未到達の状態」として扱うことで、無効な遷移を自然に排除できる点も実装上の工夫です。