最大矩阵和问题,简单DP
<!--<br />
<br />
Code highlighting produced by Actipro CodeHighlighter (freeware)<br />
http://www.CodeHighlighter.com/<br />
<br />
-->
#include<iostream>
#include<limits>
usingnamespacestd;
constintMAXSIZE=100;
inta[MAXSIZE][MAXSIZE],b[MAXSIZE],n;
intmaxSubArray()
{//计算最大子序列和
intcurSum=0,sum=numeric_limits<int>::min();
for(inti=0;i<n;i++)
{
if(curSum>0)
curSum+=b[i];
else
curSum=b[i];
if(curSum>sum)
sum=curSum;
}
returnsum;
}
intmaxSubMatrix()
{//计算最大子矩阵和
inti,j,k,curSum=0,sum=numeric_limits<int>::min();
for(i=0;i<n;i++)
{
for(k=0;k<n;k++)//初始化b[]
{
b[k]=0;
}
for(j=i;j<n;j++)//把第i行到第j行相加,对每一次相加求出最大值
{
for(k=0;k<n;k++)
{
b[k]+=a[j][k];
}
curSum=maxSubArray();
if(curSum>sum)
{
sum=curSum;
}
}
}
returnsum;
}
intmain(void)
{
cin>>n;
inti,j;
//输入矩阵
for(i=0;i<n;++i)
{
for(j=0;j<n;++j)
{
cin>>a[i][j];
}
}
cout<<maxSubMatrix()<<endl;
return0;
}
分享到:
相关推荐
zoj吐血制作,希望大家喜欢
zoj 1610 Count the Colors.md
zoj 1255 The Path.md
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
zoj 1810 The Gourmet Club.md
zoj 2499 The Happy Worm.md
zoj 2151 The Highest Profits.md
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
To prevent other companies from revealing his secret, he decided to use a substitution cipher in all the letters mentioning the new play. Substitution cipher is defined by a substitution table ...
Problem Arrangement zoj 3777
ZOJ题目答案源码
zoj 1566 Too Lazy To Move.md
一个非常非常非常非常实用的zoj结题代码
ZOJ1805代码
It costs R yuans for the theatre to run each show, and S yuans to serve each of the audiences during each show. Now your job is to write a program to maximize the total revenue of each show for the ...
zoj 1003 c语言的,要写这么多描述吗。。
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够