【C言語】行列内の2行の要素合計における最大差の求め方

問題の概要

行列が与えられたとき、その中の2つの行について「行の要素の合計の差」が最大になる組み合わせを見つけるのが本記事のテーマです。ここでは i 行 × j 列の行列 M[i,j] を想定し、行を R₀ から R_i-1 までと呼びます。差は「R_y の要素の合計 − R_x の要素の合計(ただし x < y)」という形で計算します。つまり、必ず後ろの行から前の行を引くというルールがある点に注意してください。

例題で確認しよう

入力例 1

M[4][4] = {
    { 1, 2, 0, 5 },
    { 0, 1, 1, 0 },
    { 7, 2, 3, 2 },
    { 1, 2, 4, 1 }
};

出力例 1

Maximum difference here is : 12

解説: 3行目(添字2)の合計は 7 + 2 + 3 + 2 = 14 で最大、2行目(添字1)の合計は 0 + 1 + 1 + 0 = 2 で最小です。よって最大差は 14 − 2 = 12 となります。

入力例 2

M[4][4] = {
    { 0, 2, 0, 5 },
    { 0, 1, 4, 0 },
    { 1, 2, 3, 2 },
    { 2, 2, 6, 0 }
};

出力例 2

Maximum difference here is : 5

解説: 4行目(添字3)の合計は 2 + 2 + 6 + 0 = 10 で最大、2行目(添字1)の合計は 0 + 1 + 4 + 0 = 5 で最小です。よって最大差は 10 − 5 = 5 となります。

アルゴリズムの考え方

• まず、少なくとも2行以上ある行列について、行数と列数を入力として受け取ります。

• rowmaxd() 関数に入力行列・行数・列数を渡し、行の合計同士の最大差を返り値として取得します。

• 最初に、行列 M[row][col] の各行の要素の合計を配列 RSum[i] に格納します。RSum の長さは行列の行数と同じになります。

• 続いて、最大差 MD を「RSum[1] − RSum[0]」で初期化します。RSum[0] は 0 行目の全要素の合計、RSum[1] は 1 行目の全要素の合計です。

• また、現時点での最小値として RSum[0] を仮定し、変数 MIN に保存しておきます。

• for ループで RSum の各要素を走査し、「RSum[i] − MIN > MD」であれば MD を更新します。さらに「RSum[i] < MIN」であれば MIN を個別に更新します。

この手法を使えば、すべての行ペアを総当たりで調べる O(n²) の方法と比べて、たった 1 回の走査で答えを求められます。これは株式の売買益最大化問題などでも応用される有名なテクニックです。

C言語による実装例

#include <stdio.h>
#define MAX 100

/* 後ろの行の合計から前の行の合計を引いたときの最大差を求める関数 */
int rowmaxd(int M[][MAX], int row, int col){
    /* 各行の要素の合計を格納する配列 */
    int RSum[row];
    for(int i = 0; i < row; i++){
        int sum = 0;
        for(int j = 0; j < col; j++)
            sum += M[i][j];
        RSum[i] = sum;
    }
    /* RSum[j] - RSum[i](i < j)となる2要素間の最大差を計算 */
    int MD = RSum[1] - RSum[0];
    int MIN = RSum[0];
    for(int i = 1; i < row; i++){
        /* 差が現在のMDより大きければMDを更新 */
        if(RSum[i] - MIN > MD)
            MD = RSum[i] - MIN;
        /* 値が現在のMINより小さければMINを更新 */
        if(RSum[i] < MIN)
            MIN = RSum[i];
    }
    return MD;
}

/* ドライバプログラム */
int main(){
    int r = 5, c = 4;
    int mat[][MAX] = {
        {-1, 2, 3, 4},
        {6, 3, 0, 1},
        {-1, 7, 8, -3},
        {3, 5, 1, 4},
        {2, 1, 1, 0}};
    printf("行列内の2行の要素合計の最大差: %d\n", rowmaxd(mat, r, c));
    return 0;
}

なお、可変長配列(VLA)を使用しているため、コンパイルには C99 以降に対応したコンパイラが必要です。

実行結果

上記のコードを実行すると、次の出力が得られます。

行列内の2行の要素合計の最大差: 5

計算量について

時間計算量は O(row × col)、必要な追加メモリは O(row) です。行ごとの合計を一度計算してしまえば、あとはその配列を 1 回走査するだけで最大差が求まるため、大規模な行列に対しても非常に効率的に動作します。