POJ 1050 To the MaxクラシックDP

題意:行列をあげて、最大サブ行列を求めることです.最大サブマトリクスの意味は、マトリクスの要素と最大です.
構想:この問題を最大連続サブストリングと問題、すなわち2次元を1次元に変換する.求められた最大サブマトリクスがx行からy行、c列目からr列目であると仮定すると、このマトリクスは、1次元、すなわち、1列目からn列目までのすべてのx行からy行までの要素和の最大連続サブ列和に変換される.このようにすると,複雑度nの三次方は,最大連続サブストリング和を求めるときにDPでよい.
コード:

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;

#define CLR(arr,val) memset(arr,val,sizeof(arr))
const int N = 110;
int n;
int max(int a,int b){
	return a>b?a:b;
}
int maxvalue(int vv[N]){
	int dp[N];
	CLR(dp,0);
	dp[0] = vv[0];
	for(int i = 1;i < n;++i){
	   dp[i] = max(vv[i],dp[i-1]+vv[i]);
	}
	int mmax = 0;
	for(int i = 0;i < n;++i)
		if(dp[i] > mmax)
			mmax = dp[i];
	return mmax;
}
int main(){
	//freopen("1.txt","r",stdin);
	while(scanf("%d",&n) != EOF){
	  int num[N][N];
	  int dit[N];
	  CLR(dit,0);
	  for(int i = 0;i < n;++i)
		  for(int j = 0;j < n;++j)
			  scanf("%d",&num[i][j]);
	  int ans = 0;
	  for(int i = 0;i < n;++i){
		  CLR(dit,0);
		  for(int j = i;j < n;++j){
			  for(int k = 0;k <n;++k){
			    dit[k] += num[j][k];
			  }
			  /*for(int z = 0;z < n;z++)
			  printf("%d ",dit[z]);
		      cout<<endl;*/
		      ans = max(ans,maxvalue(dit));
		  }
	  }
	  printf("%d
",ans);
	}
	return 0;
}