URAL 1146 Maximum Sum(DP)
2024-08-27 11:40:07
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.
题目大意:给一个n*n的矩阵,求和最大的子矩阵。
思路:用sum[i][j]表示从mat[1][j]~mat[i][j]的总和(从1开始计数)
然后枚举上下两行夹着的矩阵,设第一行为r1,第二行为r2,复杂度为O(n^2),然后计算这两行夹着的最大子矩阵。
用sum[r2][j] - sum[r1 - 1][j]表示mat[r1][j]~mat[r2][j]的总和。
那么,我们把r1~r2之间的列,每一列算出来,就变成了一个只有n个元素的一维数组,求最大连续子序列。
这个就是经典问题了,设a[i] = sum[r2][i] - sum[r1][i],初始化t = 0。
t从a[1]加到a[n],当t < 0的时候,令t = 0,算到 i 的时候,t就表示以a[i - 1]为结尾的最大后缀。
因为,如果我们算到a[i],此时t < 0,那么,算a[i + 1]的时候,肯定不会加上a[i]和前面的数字,不管怎么加,前面的数都小于0,还是不加的好。
能加的肯定要加上,所以复杂度为O(n)。
总复杂度为O(n^3)
代码(0.031S):
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std; const int MAXN = ; int mat[MAXN][MAXN], n;
int sum[MAXN][MAXN]; void calsum() {
for(int i = ; i <= n; ++i)
for(int j = ; j <= n; ++j) sum[i][j] = sum[i - ][j] + mat[i][j];
} int solve() {
int ans = -;
for(int r1 = ; r1 <= n; ++r1) {
for(int r2 = r1; r2 <= n; ++r2) {
int t = ;
for(int j = ; j <= n; ++j) {
t += sum[r2][j] - sum[r1 - ][j];
ans = max(t, ans);
if(t < ) t = ;
}
}
}
return ans;
} int main() {
scanf("%d", &n);
for(int i = ; i <= n; ++i)
for(int j = ; j <= n; ++j) scanf("%d", &mat[i][j]);
calsum();
printf("%d\n", solve());
}
最新文章
- 张艾迪(创始人): 整合全新的UIW.AD概念模式
- json对象数组按对象属性排序
- js引出函数概念的案例
- zabbix配置发送报警邮件
- mysql innodb 数据打捞(一)innodb 页面结构特征
- Web用户自定义控件
- iconv
- 制作Android Demo GIF:程序演示效果GIF图录制
- Android窗口管理服务WindowManagerService对窗口的组织方式分析
- Groovy与Java集成常见的坑(转)
- 这是一名Java学者关于学习方向的建议
- div,margin,padding
- Quartz.net 3.x使用总结(一)——入门介绍
- Django路由层
- git链接到远程github上
- vue 需求 data中的数据之间的调用
- springboot整合freemarker
- 如何将 Java 项目转换成 Maven 项目
- django配置数据库
- oracle 之监听保护
热门文章
- 非模态对话框的PreTranslateMessage() 没有用,无法进去
- 单选按钮控件(Ridio Button)的使用
- FW:: ehcache memcache redis 三大缓存男高音
- HBase的安装部署以及简单使用
- 【Android测试】【第二节】性能——CPU时间片
- 一张表有三个字段:id(城市id) Cityname(城市名) Privence(所属省份)如果要统计每个省份有多少城市请用SQL实现。
- php——n维数组的遍历——递归
- 高效的两段式循环缓冲区──BipBuffer
- [LeetCode]题解(python):034-Search for a Range
- GIS 学习及参考站点