C++で解く：2×nグリッドにおいて隣接しない要素を選ぶときの最大合計

この問題では、サイズ 2 × n の長方形グリッドが与えられます。縦・横・斜めのいずれの方向にも隣接しないように要素を選んだときの最大合計を求めるプログラムを、C++で作成していきましょう。

問題の概要

最大合計を求めるにあたっては、現在注目している要素に対して、縦・横・斜めのどの方向で隣接している要素も一緒に選択することはできません。

具体例で問題を確認してみましょう。

入力

rectGrid[2][] = {{3, 8, 9},
                 {4, 1, 1}}

出力

13

解説

考えられるすべての選び方とその合計は、以下のようになります。

• rectGrid[0][0] の値「3」から始める場合：加算できるのは「9」または「1」のみ。最大合計は 12。
• rectGrid[1][0] の値「4」から始める場合：加算できるのは「9」または「1」のみ。最大合計は 13。
• rectGrid[0][1] の値「8」から始める場合：隣接制約により他の要素を一切加算できない。最大合計は 8。
• rectGrid[1][1] の値「1」から始める場合：同様に他の要素を加算できない。最大合計は 1。
• rectGrid[0][2] の値「9」から始める場合：加算できるのは「3」または「4」のみ。最大合計は 13。
• rectGrid[1][2] の値「1」から始める場合：加算できるのは「3」または「4」のみ。最大合計は 5。

以上より、全体の最大合計は 13 であることがわかります。

解法のアプローチ

この問題は、以前の記事で取り上げた「隣接しない要素の最大合計」問題と非常によく似ています。異なる点は、配列が2次元になっていることと、隣接要素の条件の定義です。

そこで本解法では、行と列の両方の条件を踏まえて最大値を考えていきます。各列には2行分の要素が存在するため、まず各列ごとの大きい方の値に着目します。そして、「その列の値を採用する場合（currectSum）」と「採用せずスキップする場合（nextSum）」という2つの状態を交互に更新していくことで、動的計画法のように効率よく最大合計を求められます。

アルゴリズムの流れは次の通りです。

1. 現在の合計（currectSum）と直前までの合計（nextSum）を 0 で初期化します。
2. 各列について、まず「その列を選ばない場合の最大値」として nextSum と currectSum の大きい方を退避します（altSum）。
3. currectSum を「nextSum ＋ 現在の列の2要素のうち大きい方」として更新します。
4. nextSum を手順2で退避した altSum で更新し、これを最後の列まで繰り返します。
5. 最終的に nextSum と currectSum の大きい方が答えとなります。

C++実装例

上記の解法の動作を示すプログラムがこちらです。

#include<iostream>
using namespace std;

int findMax(int a, int b){
    if(a > b)
        return a;
    return b;
}

int calcMaxSum(int rectGrid[2][20], int N){
    int currectSum = 0;
    int nextSum = 0;
    int altSum;
    for (int i = 0; i<N; i++){
        altSum = findMax(nextSum, currectSum);
        currectSum = nextSum + findMax(rectGrid[0][i], rectGrid[1][i]);
        nextSum = altSum;
    }
    int maxSum = findMax(nextSum, currectSum);
    return maxSum;
}

int main(){
    int rectGrid[2][20] = {{3, 8, 9, 5},
        {4, 1, 2, 7}};
    int N = 4;
    cout<<"The maximum sum in a 2 x "<<N<<" grid such that no two elements are adjacent is "<<calcMaxSum(rectGrid, N);
    return 0;
}

出力

The maximum sum in a 2 x 4 grid such that no two elements are adjacent is 15

まとめ

このように、各列の最大値に着目し「その列を選ぶ／選ばない」という2つの状態を管理するだけで、縦・横・斜めの隣接制約を満たす最大合計を求められます。グリッドを一度走査するだけで処理が完了するため、時間計算量は O(n)、必要な追加メモリは定数 O(1) という非常に効率的な解法です。「隣接しない要素の最大和」系の問題は応用範囲が広いため、このパターンはぜひマスターしておきましょう。