AOJ 0098 Maximum Sum Sequence II

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0098

問題概要

n次正方行列(a_ij)が与えられる．(a_ij) の部分行列の要素の和の最大値を求めよ．

・制約
1 <= n <= 100

解法

まず，要素の横方向について累積和を取る．
その後，横方向のある区間[i, j]を固定して考えてみる．
この区間の第 k 行の和はsum[k][j] - sum[k][i] である．
Sij[k] := sum[k][j] - sum[k][i] (k = 0, ... , N-1)とおく．
すると，この区間の幅を考えたときの最大値は，Sij[k] の連続する部分列の和の最大値を求める問題に帰着できる．
これは動的計画法でとけるので，最終的な計算量は O(N^3)である．

ソースコード

#include <iostream>
#include <vector>
using namespace std;
 
using ll = long long;
 
int main() {
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for(int i=0; i<n; ++i) {
        for(int j=0; j<n; ++j) {
            cin >> a[i][j];
        }
    }
    vector<vector<int>> sum(n, vector<int>(n+1));
    for(int i=0; i<n; ++i) {
        for(int j=0; j<n; ++j) {
            sum[i][j+1] += sum[i][j] + a[i][j];
        }
    }
    int res = -1e9;
    for(int i=0; i<=n; ++i) {
        for(int j=i+1; j<=n; ++j) {
            int t = 0;
            for(int k=0; k<n; ++k) {
                if(t < 0) {
                    t = sum[k][j] - sum[k][i];
                } else {
                    t += sum[k][j] - sum[k][i];
                }
                res = max(res, t);
            }
        }
    }
    cout << res << endl;
}