暴力：
O(n6)
O(n4)解法
vector<vector<int>> CalculateMap(vector<vector<int>> mat)
{
vector<vector<int>> map(mat.size(),vector<int>(mat.front().size(),0));
for (int i = 0; i < mat.size(); i++)
{
for (int j = 0; j < mat.front().size(); j++)
{
if (i==0&&j==0)
{
map[i][j]=mat[i][j];
}
else if (i==0)
{
map[i][j]=map[i][j-1]+mat[i][j];
}
else if (j==0)
{
map[i][j]=map[i-1][j]+mat[i][j];
}
else
{
map[i][j]=map[i-1][j]+map[i][j-1]-map[i-1][j-1]+mat[i][j];
}
}
}
return map;
}
int CalculateSum(vector<vector<int>> mat,int i,int j,int k ,int w,vector<vector<int>> map)
{
int sum;
if (i==0&&k==0)
{
sum=map[j][w];
}
else if (i==0)
{
sum=map[j][w]-map[j][k];
}else if (k==0)
{
sum=map[j][w]-map[i][w];
}
else
{
sum=map[j][w]-map[i-1][w]-map[j][k-1]+map[i-1][k-1] ;
}
;
return sum;
}
int sumOfSubMatrix(vector<vector<int> > mat, int n)
{
int MaxSum=mat.front().front();
vector<vector<int>> map;
map=CalculateMap(mat);
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
for (int k = 0; k < n; k++)
{
for (int w = k; w < n; w++)
{
if (CalculateSum(mat,i,j,k,w,map)>MaxSum)
{
MaxSum=CalculateSum(mat,i,j,k,w,map);
}
}
}
}
}
return MaxSum;
}
动态规划
O(n4):肯定比上一个要小，估计是O(n3.5)左右，反正可以跑起来
int GetBigger(int x, int y)
{
return x>y?x:y;
}
int GetMaxArray(vector<int> a,int n)
{
vector<int> start(n,0);
vector<int> all(n,0);
start[n-1]=all[n-1]=a[n-1];
for (int i = n-2; i >=0; i--)
{
start[i]=GetBigger(start[i+1]+a[i],a[i]);
all[i]=GetBigger(start[i],all[i+1]);
}
return all[0];
}
int MaxofIJ(vector<vector<int>> mat,int n,int i, int j)
{
vector<int> a(n,0);
for (int k = 0; k < n; k++)
{
for (int Count = i; Count <=j; Count++)
{
a[k]+=mat[Count][k];
}
}
return GetMaxArray(a,n);
}
int sumOfSubMatrix(vector<vector<int> > mat, int n)
{
int Maxsum=mat.front().front();
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
if (Maxsum<MaxofIJ(mat,n,i,j))
{
Maxsum=MaxofIJ(mat,n,i,j);
}
}
}
return Maxsum;
}
动态规划O(n3)
int GetBigger(int x, int y)
{
return x>y?x:y;
}
int GetMaxArray(vector<int> a,int n)
{
vector<int> start(n,0);
vector<int> all(n,0);
start[n-1]=all[n-1]=a[n-1];
for (int i = n-2; i >=0; i--)
{
start[i]=GetBigger(start[i+1]+a[i],a[i]);
all[i]=GetBigger(start[i],all[i+1]);
}
return all[0];
}
int sumOfSubMatrix(vector<vector<int> > mat, int n)
{
int Maxsum=mat.front().front();
for (int i = 0; i < n; i++)
{
vector<int> a(mat.front().size(),0);
for (int j = i; j < n; j++)
{
for (int k = 0; k < n; k++)
{
a[k]+=mat[j][k];
}
if (Maxsum<GetMaxArray(a,n))
{
Maxsum=GetMaxArray(a,n);
}
}
}
return Maxsum;
}