3つ連続しない条件での最大部分列の合計をC++で解く方法

本記事では、「同じ位置の要素を3つ連続して選ばない」という制約のもとで、数列から選んだ要素の合計を最大化する問題を解くプログラムについて解説します。

具体的には、正の整数列が与えられたとき、部分列として要素を選んでいく過程で3つ連続した要素を同時に選ぶことはできません。この条件下で実現できる合計値の最大値を求めるのが目的です。

動的計画法によるアプローチ

この問題は動的計画法(DP)を用いることで効率的に解くことができます。位置 i までの最大合計を sum[i] とするとき、i 番目の要素の扱い方は以下の3通りに分けられます。

• i 番目を選ばない場合: sum[i-1]
• i 番目だけを選ぶ場合(i-1 番目は選ばない): sum[i-2] + arr[i]
• i 番目と i-1 番目の両方を選ぶ場合(i-2 番目は選ばない): arr[i] + arr[i-1] + sum[i-3]

これら3つの候補の中から最大値を sum[i] として記録していき、最終的な sum[n-1] が答えとなります。計算量は O(n)、必要なメモリも O(n) であり、全探索よりもはるかに高速に処理できます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
// 3つ連続の数字を含まない最大部分列の合計を返す
int maxSumWO3Consec(int arr[], int n) {
   int sum[n];
   if (n >= 1) sum[0] = arr[0];
   if (n >= 2) sum[1] = arr[0] + arr[1];
   if (n > 2) sum[2] = max(sum[1], max(arr[1] + arr[2], arr[0] + arr[2]));
   for (int i = 3; i < n; i++)
      sum[i] = max(max(sum[i - 1], sum[i - 2] + arr[i]),
                     arr[i] + arr[i - 1] + sum[i - 3]);
   return sum[n - 1];
}
int main() {
   int arr[] = { 100, 1000 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << maxSumWO3Consec(arr, n);
   return 0;
}

出力結果

1100

コードの解説

初期化部分では、配列の長さが1の場合は最初の要素そのものが答えになり、長さが2の場合は2つの要素の合計がそのまま答えになります。これは2つまでなら連続して選んでもよいというルールのためです。長さが3以上の場合は、3つのうち少なくとも1つは必ず除外されるため、その組み合わせごとの最大値を計算します。

サンプル入力 {100, 1000} の場合、要素は2つしかないため両方を選ぶことが可能で、合計は 100 + 1000 = 1100 となります。