C++で解く「K以下の最大の長方形領域の合計」問題：効率的なアルゴリズムと実装

問題概要

2次元行列と整数 k が与えられたとき、行列内の長方形領域のうち、その合計値が k を超えないものの中で最大の合計値を求めます。

例として、次のような入力を考えてみましょう。

このとき k = 3 であれば、緑色で示した長方形領域（1 + 2）の合計がちょうど 3 となり、これが答えになります。

アルゴリズムの考え方

この問題は、列の組み合わせごとに行方向の累積和を求め、二分探索（lower_bound）を使って条件を満たす最大値を効率よく探すことで解決できます。手順は以下の通りです。

• 関数 maxSumSubmatrix() を定義し、2次元配列 matrix と整数 k を受け取ります。
• n := 行数、m := 列数、ans := -∞（INT_MIN）と初期化します。
• 左端の列 l を 0 から m-1 まで順に動かします。
  • サイズ n の配列 rowSum を用意します。
• 右端の列 r を l から m-1 まで順に動かします。
  • 各行 i について rowSum[i] に matrix[i][r] を加算し、l 列目から r 列目までの行ごとの合計を保持します。
  • 集合（set）s を定義し、0 を挿入しておきます。
  • currSum := 0 と初期化します。
  • 各行 i について以下を繰り返します。
    • currSum に rowSum[i] を加算します。
    • 集合 s の中から「currSum − k 以上となる最小の要素」を二分探索で取得します。
    • その要素が存在すれば、ans を ans と (currSum − その要素) の最大値で更新します。
    • currSum を集合 s に挿入します。
• 最後に ans を返します。

この手法により、時間計算量は O(min(n,m)² × max(n,m) × log(max(n,m))) となり、全長方形を素朴に列挙する方法より大幅に高速化できます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int m = matrix[0].size();
        int ans = INT_MIN;
        for(int l = 0; l < m; l++){
            vector <int> rowSum(n);
            for(int r = l; r < m; r++){
                for(int i = 0; i < n; i++)rowSum[i] += matrix[i][r];
                set < int > s;
                s.insert(0);
                int currSum = 0;
                for(int i = 0; i < n; i++){
                    currSum += rowSum[i];
                    set <int> :: iterator it = s.lower_bound(currSum - k);
                    if(it != s.end()){
                        ans = max(ans, (currSum - *it));
                    }
                    s.insert(currSum);
                }
            }
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{1,0,1},{0,-3,2}};
    cout << (ob.maxSumSubmatrix(v, 3));
}

入力

[{1,0,1},{0,-3,2}]
3

出力

3

まとめ

このアルゴリズムのポイントは、列のペア（左端・右端）を固定して行方向の累積和に変換した上で、set の lower_bound を活用して「k を超えない最大の部分和」を対数時間で見つけるところにあります。負の値を含む行列でも正しく動作するため、応用範囲の広い実用的なテクニックです。