UVa108

題敘

http://domen111.github.io/UVa-Easy-Viewer/?108
給一個 $n \times n$ 的陣列，求最大的子區域元素和

想法

枚舉直行的左界右界，從最上列開始往下加，每次更新最大答案
在列的部分希望能做到 $O(1)$ 求解
可以想到前綴和，將每列的元素與前一個元素相加
$sum[i][j] = sum[i][j-1] + arr[i][j]$
如此一來當我們想求第 $i$ 列的 $j$～$k$行元素總和
$sum[i][k]-sum[i][j-1]$即可得解

Code

//By Koios1143
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
int n,arr[105][105],col[105][105];
int main(){
	IOS
	cin>>n;
	for(int i=1 ; i<=n ; i++){
		for(int j=1 ; j<=n ; j++){
			cin>>arr[i][j];
			col[i][j] = col[i][j-1]+arr[i][j];
		}
	}
	int ans=0;
	for(int i=1 ; i<=n ; i++){
		for(int j=i ; j<=n ; j++){
			int sum=0;
			for(int k=1 ; k<=n ; k++){
				sum+=col[k][j]-col[k][i-1];
				ans=max(ans,sum);
				if(sum<0) sum=0;
			}
		}
	}
	cout<<ans<<"\n";
	return 0;
}

複雜度

$O(n^2)$