c语言 这道题该怎么做?没有思路

 我来答
匿名用户
2019-12-06
展开全部

最大子矩阵,最大连续子数组进阶,动态规划初级,poj1050

题目描述:现给出一个N*N矩阵,要求求出拥有最大和的子矩阵的和。

例如:

这样的一个矩阵,最大子矩阵的和为15;

此题可以让人联想到求最大连续子数组,求最大子数组在上一篇文章中http://www.cnblogs.com/tz346125264/p/7560708.html。

分析:最大子矩阵可以看为求最大连续子数组拓展到二维数组上,因为矩阵的性质同样在横向竖向上需要连续,那么可以想办法将这个二维数组简化为求连续子数组。

思考:

1.要求最大子矩阵,必须保证每个矩阵都被浏览到,为了保证运行时间尽可能不要重复浏览同一矩阵,故需制定规则,规则定为用i表示起始行,j表示终止行,j>=i,再使用k对列进行遍历,即可覆盖所有矩阵。

2.进行化简成求连续子数组操作,以上为例,设i=2,j=4那么这个矩阵是这样,那么化为连续子数组即为4(9-4-1),11(2+1+8),-10(-6-4+0),1(2+1-2)

求这个连续数组的最大连续子数组和便是这个矩阵(以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;
}

qwe964157723
2019-12-06
知道答主
回答量:9
采纳率:0%
帮助的人:3.4万
展开全部

百度贪心算法有详细说明介绍,说实话这道题我最简单最麻烦的做法要把所有的矩阵出现的例子都对比一下,看谁大,因为我不是数学家,所以我推荐你百度下列关键词

求子数组的最大值(贪心算法)

已赞过 已踩过<
你对这个回答的评价是?
评论 收起
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询
?>

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式