C++で行列の任意の部分行列から得られる最大トレースを求める方法

本記事では、二次元配列 arr[][] が与えられたとき、その中から選べる任意の部分行列について考えられる最大トレースを求めるC++プログラムを紹介します。

問題の概要

トレースとは、正方行列の主対角線上の要素をすべて足し合わせた値のことです。この問題では、与えられた行列から取り出せるすべての部分行列を対象に、そのトレースの最大値を見つける必要があります。

入力例

arr[][] = {{-2, 5, 3},
           { 1, 6, 2},
           { 4, 3, 9}}

出力例

15

解説

対象となる部分行列: {6, 2}
                   {3, 9}

この部分行列の主対角線上の要素は「6」と「9」であるため、トレースは 6 + 9 = 15 となり、これが最大値になります。

解法アプローチ

最もシンプルな解き方は、行列内のすべてのセルを始点として、そこから右下方向へ対角線に沿って要素を順に加算していき、途中経過の和（トレース）が最大となるタイミングを記録する方法です。これは一次元配列の最大部分配列和を求める際に使われる「カダネのアルゴリズム（Kadane's algorithm）」の考え方を、対角線方向に応用したものと言えます。

各ステップで現在の累積和とこれまでの最大値を比較し、大きければ答えを更新します。N×N の行列の場合、計算量は O(N²) となり、効率的に解くことができます。なお、すべての要素が負のケースも厳密に扱いたい場合は、初期値を最初の対角要素または INT_MIN に設定すると安全です。

C++での実装例

以下は、本解法の動作を示すサンプルプログラムです。

#include <iostream>
using namespace std;
#define row 3
#define col 3

int CalcMaxTraceSubMat(int mat[row][col]){
    int maxtraceSum = 0, r, c, traceSum;
    for (int i = 0; i < row; i++){
        for (int j = 0; j < col; j++){
            r = i, c = j, traceSum = 0;
            while (r < row && c < col){
                traceSum += mat[r][c];
                r++;
                c++;
                maxtraceSum = max(traceSum, maxtraceSum);
            }
        }
    }
    return maxtraceSum;
}

int main() {
    int mat[row][col] = { {-2, 5, 3},
                          { 1, 6, 2},
                          { 4, 3, 9} };

    cout << "部分行列として考えられる最大トレースは "
         << CalcMaxTraceSubMat(mat);
    return 0;
}

実行結果

部分行列として考えられる最大トレースは 15

まとめ

この問題は、カダネのアルゴリズムの発想を行列の対角線方向に適用することで、全ての部分行列を明示的に生成することなく O(N²) で効率よく解くことができます。対角線上の連続する要素の和としてトレースを捉える視点が、シンプルかつ強力な鍵となります。