【C++解説】配列内で隣接しない要素同士の最大合計を求める方法

この記事では、配列 arr[] が与えられたときに、「選んだ2つの要素が元の配列内で隣り合わない」という条件を満たす最大合計を求めるプログラムをC++で実装する方法を解説します。

問題の概要

配列の中からいくつかの要素を選び、その合計を最大化することを考えます。ただし、選んだ要素どうしが元の配列内で隣接してはいけないという制約が付きます。この条件のもとで達成できる最大の合計値を求めるのが本問題です。

具体例を見てみましょう。

入力

arr[] = {5, 1, 3, 7, 9, 2, 5}

出力

22

解説

インデックス0から1つおきに要素を選んだ場合 : 5 + 3 + 9 + 5 = 22
インデックス1から1つおきに要素を選んだ場合 : 1 + 7 + 2 = 10

このとき、制約を満たす合計の最大値は 22 となります。

解決アプローチ

この問題は、配列の各要素を順番に走査しながら、次の2つの合計値を管理することで効率よく解けます。

• maxSum1(現在の要素を含める場合の合計): 直前までの「含めない合計」に現在の要素を加えた値
• maxSum2(現在の要素を含めない場合の合計): 直前の時点での両者のうち大きい方の値

各反復処理では、まず一時変数 temp に max(maxSum1, maxSum2) を保存し、次に maxSum1 を「maxSum2 + 現在の要素」で更新、最後に maxSum2 を temp の値で更新します。ループが終了した時点で、max(maxSum1, maxSum2) が求める答えになります。

この手法は動的計画法(DP)の応用であり、時間計算量は O(N)、空間計算量は O(1) と非常に効率的です。

サンプルプログラム

以下は、この解法の動作を示すC++プログラムです。

#include<iostream>
using namespace std;
int findmaximum(int a, int b){
   if(a > b)
      return a;
      return b;
}
int findMaxSumWOAdjecent(int arr[], int N){
   int maxSum1 = arr[0];
   int maxSum2 = 0;
   int temp;
   for (int i = 1; i < N; i++) {
      temp = findmaximum(maxSum1, maxSum2);
      maxSum1 = maxSum2 + arr[i];
      maxSum2 = temp;
   }
   return (findmaximum(maxSum1, maxSum2));
}
int main(){
   int arr[] = {5, 1, 3, 7, 9, 2, 5};
   int N = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum sum such that no two elements are adjacent is "<<findMaxSumWOAdjecent(arr, N);
   return 0;
}

実行結果

The maximum sum such that no two elements are adjacent is 22

このように、たった1回の走査で隣接しない要素同士の最大合計を求めることができます。同様のパターンは「House Robber問題」などでも応用される重要なアルゴリズムなので、ぜひマスターしておきましょう。