Zerojudge b840

題目

https://zerojudge.tw/ShowProblem?problemid=b840

給一個 $n \times n$ 的陣列，求最大矩形和

想法

暴力枚舉左上角的點以及長寬，將答案加總後取最大值

因為本題題目範圍很小可以這樣做

Code

//By Koios1143
#include<iostream>
using namespace std;
int n,arr[25][25],ans=0,cnt=0;
int main(){
	cin>>n;
	for(int i=0 ; i<n ; i++){
		for(int j=0 ; j<n ; j++){
			cin>>arr[i][j];
		}
	}
	for(int i=0 ; i<n ; i++){
		for(int j=0 ; j<n ; j++){
			for(int k=0 ; k+i<n ; k++){
				for(int l=0 ; l+j<n ; l++){
					cnt=0;
					for(int p=i ; p<=i+k ; p++){
						for(int q=j ; q<=j+l ; q++){
							cnt+=arr[p][q];
						}
					}
					ans=max(cnt, ans);
				}
			}
		}
	}
	cout<<ans<<"\n";
	return 0;
}

複雜度分析

總時間複雜度為 $O(n^2 + n^6)$