質問は：
2D 配列 [1:m,1:n] が与えられた場合、1<=a<=b<=m および 1<=c<=d である部分配列の最大和 [a:b,c:d] を見つける必要があります。 <=n で、配列の要素の合計が (Summation)A[i,j] となるように、時間計算量 O(mn min(m,n ) log max(m,n))
問題の解決方法を知りたいのですが、次のように考えていました-
1) 各行で Kadane のアルゴリズムを使用して、2x2 行列の中央から左右に向かって各要素の累積和を求めます。
2) 昇順に基づいて右側の合計を並べ替えます
3)左側の各要素を右側の最大要素にマップし、最大値を持つ行を選択します。
4)2×2の行列の真ん中から上下に向かって同じ手順を繰り返す(累積和)
5) 手順 2 と 3 を繰り返します。
6) 両方の方法で得られた最大値を結合し、それを最大合計部分配列として使用します