1146. Maximum Sum

Time limit: 1.0 second Memory limit: 64 MB
Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. A sub-rectangle is any contiguous sub-array of size 1 × 1 or greater located within the whole array.
As an example, the maximal sub-rectangle of the array:
0 −2 −7 0
9 2 −6 2
−4 1 −4 1
−1 8 0 −2
is in the lower-left-hand corner and has the sum of 15.

Input

The input consists of an N × N array of integers. The input begins with a single positive integer Non a line by itself indicating the size of the square two dimensional array. This is followed by N 2integers separated by white-space (newlines and spaces). These N 2 integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on the second row, left-to-right, etc.). N may be as large as 100. The numbers in the array will be in the range [−127, 127].

Output

The output is the sum of the maximal sub-rectangle.

Sample

input output
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
15

题意:输入部分第一行是一个正整数N,说明矩阵的大小。下一行后面跟着 个整数。留意这些整数的输入格式可能比较混乱。矩阵是以行优先存储的。N可能和100一样大,矩阵中每个数字的范围为 [-127, 127].

思路1:对矩阵进行穷举。找出所有的子矩阵计算矩阵和并找出最大值。

 #include<iostream>
#include<cstdio>
#include<string>
#include<cstring> using namespace std;
int s[][]= {};
int dp[][]= {}; int main()
{
// freopen("1.txt","r",stdin);
int i,j,ki,kj;
int n;
while(cin>>n)
{
for(i=; i<=n; i++)
for(j=; j<=n; j++)
{
cin>>s[i][j];
s[i][j]+=s[i-][j];
s[i-][j]+=s[i-][j-];
}//输入矩阵并且计算从(1,1)到(i-1,j)的矩阵的和值
for(i=; i<=n; i++)
s[n][i]+=s[n][i-];//计算从(1,1)到(n,i)的矩阵的和值
int max=-;//特别注意因为
for(i=; i<=n; i++)
for(j=; j<=n; j++)
{
max=-;
for(ki=; ki<i; ki++)
for(kj=; kj<j; kj++)
if(max<s[i][j]-s[i][kj]-s[ki][j]+s[ki][kj])//计算(ki,kj)到(i,j)的子矩阵的和并且和max比较;
max=s[i][j]-s[i][kj]-s[ki][j]+s[ki][kj];
dp[i][j]=max;
}
max=-;
for(i=; i<=n; i++)
for(j=; j<=n; j++)
if(max<=dp[i][j])
max=dp[i][j];
cout<<max<<endl;
}
return ;
}

思路2求最大子矩阵的和,先按列进行枚举起始列和结束列,用数据够快速求出每行起始列到结束列之间各数据的和,然后就可以降成一维的,问题就变成了求最大连续子序列了

 #include<cstdio>
#include<cstring>
#include<iostream> using namespace std; #define N 1100
#define INF 0x3f3f3f3f
int s[N][N]= {},dp[N],n; void get_sum(int x ,int y)
{
for(int i=; i<=n; i++)
{
dp[i]=s[y][i]-s[x-][i];
}
return ;
} int DP()
{
int sum=,max=-INF;
for(int i=; i<=n; i++)
{
sum+=dp[i];
max=sum>max?sum:max;
if(sum<) sum=;
}
return max;
} int main()
{
int i,j;
// freopen("1.txt","r",stdin);
while(cin>>n)
{
for(i=; i<=n; i++)
for(j=; j<=n; j++)
{
cin>>s[i][j];
s[i][j]+=s[i-][j];
}//输入矩阵并且计算从(1,j)到(i,j)的矩阵的和值
int max=-INF,ans;
for(i=; i<=n; i++)
for(j=i; j<=n; j++)
{
get_sum(i,j);
ans=DP();
max=ans>max?ans:max;
}
printf("%d\n",max);
}
return ;
}

最新文章

  1. 在macOS Sierra 10.12搭建PHP开发环境
  2. CSS中margin和padding的区别
  3. 20.C#LINQ基础和简单使用(十一章11.1-11.2)
  4. 凡聊过必留下痕迹-破解加密的WeChat数据库
  5. flex 4 布局样式
  6. Eclipse使用jre的原理与配置
  7. [liu yanling]测试小结
  8. python邮件收发SAMPLE
  9. (23)unity4.6学习Ugui中国文档-------非官方Demo1
  10. MVP技术沙龙上海站-SQL BI
  11. ireport图形化界面生成pdf文档
  12. 2016-2017 National Taiwan University World Final Team Selection Contest
  13. python之装饰器函数
  14. SpringMvc 文件下载 详解
  15. C# Web 数据注解Data Annotations、模型状态ModelState、数据验证
  16. 获取WebService的请求信息
  17. 【AI in 美团】深度学习在OCR中的应用
  18. (转载)GRASP职责分配原则
  19. iis日志时间与本地日期不一样
  20. Python3中实现简单的购物车程序

热门文章

  1. Hibernate 命名查询
  2. J2EE 邮件发送那些事儿
  3. NOI 题库 9272 题解
  4. 【安卓】安卓res文件夹下的资源文件与R.java文件里面类的对应关系
  5. CentOS手动编译安装gcc
  6. iOS10 拍照崩溃问题
  7. GisUtil工具类:将WKT(wellKnownText)文本转换为ElasticSearch识别的空间对象字符串形式
  8. javascript中的 类初始化,遍历for in 以及with的用法
  9. 用开源Look&amp;Feel (Substance)写 漂亮的Swing应用程序
  10. only one is important
  11. c库函数之scanf
  12. HW4.33
  13. WinForm窗体的托盘最小化实现代码
  14. DOM方法
  15. 3527: [Zjoi2014]力
  16. 【web开发问题】HTTP请求POSTDATA中包含多层对象如何获取?
  17. Delphi窗体最大化按钮不可用情况下的最大化
  18. ELK 之二:ElasticSearch 和Logstash高级使用
  19. PAT (Advanced Level) 1069. The Black Hole of Numbers (20)
  20. Mac系统占用空间大、空间不够、查看系统文件大小分布