c语言 这道题该怎么做?没有思路
最大子矩阵，最大连续子数组进阶，动态规划初级，poj1050
题目描述：现给出一个N*N矩阵，要求求出拥有最大和的子矩阵的和。
例如：
这样的一个矩阵，最大子矩阵的和为15；
此题可以让人联想到求最大连续子数组，求最大子数组在上一篇文章中http://www.cnblogs.com/tz346125264/p/7560708.html。
分析：最大子矩阵可以看为求最大连续子数组拓展到二维数组上，因为矩阵的性质同样在横向竖向上需要连续，那么可以想办法将这个二维数组简化为求连续子数组。
思考：
1.要求最大子矩阵，必须保证每个矩阵都被浏览到，为了保证运行时间尽可能不要重复浏览同一矩阵，故需制定规则，规则定为用i表示起始行，j表示终止行，j>=i，再使用k对列进行遍历，即可覆盖所有矩阵。
2.进行化简成求连续子数组操作，以上为例，设i=2,j=4那么这个矩阵是这样
求这个连续数组的最大连续子数组和便是这个矩阵（以i=2作为起始行，j=4作为终止行）的最大子矩阵，如此，整个矩阵的最大子矩阵便是这些最大子矩阵中的最大值。
上代码：
#include<iostream>#include<cstring>using namespace std;int main(){ int n; int a[101][101]; int temp[101];
cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){
cin>>a[i][j]; /*
为什么要进行相加？
在化简为求连续最大子数组时，需要将i到j行的数进行相加sum(i,j)，而这个sum{i,j}可有sum{0,j}-sum{0,i}得到
为此提前做出相加方便之后化简
*/
a[i][j]+=a[i-1][j];
}
} int max = -10000; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){
memset(temp,0,sizeof(temp)); //求最大连续子数组操作
for(int k=1;k<=n;k++){ if(temp[k-1]>=0){
temp[k]=temp[k-1]+a[j][k]-a[i][k];
}else{
temp[k]=a[j][k]-a[i][k];
} if(temp[k]>max){
max = temp[k];
}
}
}
}
cout<<max<<endl; return 0;
}
百度贪心算法有详细说明介绍，说实话这道题我最简单最麻烦的做法要把所有的矩阵出现的例子都对比一下，看谁大，因为我不是数学家，所以我推荐你百度下列关键词
求子数组的最大值（贪心算法）
