読者です 読者をやめる 読者になる 読者になる

AOJ 0098 Maximum Sum Sequence II

問題概要

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

・制約
1 <= n <= 100

解法

まず,要素の横方向について累積和を取る.
その後,横方向のある区間[i, j]を固定して考えてみる.この区間の各行の和はsum[k][j] - sum[k][i] である.
S[k] := sum[k][j] - sum[k][i] とおく.
すると,この区間の幅を考えたときの最大値は,S[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;
}