1114-Get a Rectangular Field

問題概要
5x5のマス目の情報が与えられる。
中に入る最大の長方形の面積を求めよ。

考え方
ヒストグラムの最大長方形だと見なすことで
蟻本p280の考え方が利用出来る。
ただ、5x5なので普通に全探索しても良いかも。
実装(C++)

#include <iostream>
using namespace std;
/*ヒストグラムの最大長方形*/

const int MAX_N=5;
int n; //ヒストグラムの個数
int h[MAX_N]; //ヒストグラムのデーター

long long solve(){
	int L[MAX_N],R[MAX_N],st[MAX_N];
	//Lの計算
	int t=0;
	for(int i=0;i<n;i++){
		while(t>0&&h[st[t-1]]>h[i])t--;
		L[i]=t==0?0:(st[t-1]+1);
		st[t++]=i;
	}
	//Rの計算
	t=0;
	for(int i=n-1;i>=0;i--){
		while(t>0&&h[st[t-1]]>=h[i])t--;
		R[i]=t==0?n:st[t-1];
		st[t++]=i;
	}
	long long res=0;
	for(int i=0;i<n;i++){
		res=max(res,(long long)h[i]*(R[i]-L[i]));
	}
	return res;
}


int main() {
	int M[5][5];
	int T;
	cin>>T;
	for(;T--;){
		for(int i=0;i<5;i++)
			for(int j=0;j<5;j++)
				cin>>M[i][j];
		int res=0;
		for(int i=0;i<5;i++){
			for(int j=3;j>=0;j--){
				if(M[i][j])M[i][j]=M[i][j]+M[i][j+1];
			}
		}
		for(int i=0;i<5;i++){
			n=5;
			for(int j=0;j<5;j++){
				h[j]=M[j][i];
			}
			res=max(res,(int)solve());
		}
		cout<<res<<endl;
	}
	return 0;
}