题目描述
为了更好的备战 NOIP2013,电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为,我们不光需要机房,我们还需要运动,于是就决定找校长申请一块电脑组的课余运动场地,听说她们都是电脑组的高手,校长没有马上答应他们,而是先给她们出了一道数学题,并且告诉她们:你们能获得的运动场地的面积就是你们能找到的这个最大的数字。
输入
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
输出
15
动态规划
这个题可以看做是“最大字段和”在高维的情况。
具体思路是:枚举top行和bottom行,求这几行的每一列的列和,得到一个一维数组,求这个数组的最大子段和。求列和时,因为bottom是递增的,每次bottom+1之后,对应列的列和+arr[bottom]
#include
#include
#include
using namespace std;
int maxsum(int arr[],int n){
int pre=arr[0];
int res=pre;
for(int i=1;i<n;i++){
pre=max(pre+arr[i],arr[i]);
res=max(res,pre);
}
return res;
}
int main(){
int n;
cin>>n;
int arr[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>arr[i][j];
}
}
int res=INT_MIN;
for(int top=0;top<n;top++){
int sum[n];
memset(sum,0,sizeof(sum));
for(int bottom=top;bottom<n;bottom++){
for(int i=0;i<n;i++){
sum[i]+=arr[bottom][i];
}
int curmax=maxsum(sum,n);
res=max(res,curmax);
}
}
cout<<res;
return 0;
}