最大子阵 DP or 前缀和orb暴力 能过
2024-09-08 06:13:37
在一个给定的n*m二维矩阵中求一个子矩阵元素和的最大值。
思路:
1:一个二维矩阵由两个点可以确定,枚举两个点,取子矩阵最大值。
2:在一维矩阵中,求一个序列的最大子段,利用 f[i]=max(f[i-1]+a[i],a[i]); f[i]代表以i为尾的字段最大的和,a[i]代表 i此处值。 当求二维子阵的时候,因为是相邻的行和列组成矩阵,所以可以枚举连续的行或者列求和为一位子序列然后又转化为求一维的最大子段。枚举使用O(N^2),求解O(N),综合为为O(N^3);
在求连续的行中计算每列和可以采用每列一维前缀和或者开一个数组来记。
import java.util.*;
public class Main {
public static void main (String[]args){
Scanner s=new Scanner(System.in);
final int N=10005;
int[][] dp=new int[N][N];
int[] r = new int[N];
int n=s.nextInt(),m=s.nextInt();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dp[i][j]=s.nextInt();
int sum=0;
for(int i=1;i<=n;i++)
{
Arrays.fill(r,0);
for(int j=i;j<=n;j++)
{
int num=0;
for(int k=1;k<=m;k++)
{
r[k]+=dp[j][k];
if(num<0)num=r[k];
else num+=r[k];
sum=Math.max(sum,num);
}
} }
System.out.println(sum);
}
}
最新文章
- Ubuntu 登录锐捷 网卡被禁用 网口灯不亮解决
- 软件测试第六周学习笔记之“Win8 APP应用程序的白盒测试”
- 张洋:浅析PageRank算法
- SSIS的CheckPoint用法
- U型进度条
- 关于学习是UIWebView的一些思考
- CSS的position(位置)
- hdu 神、上帝以及老天爷
- My Sql多表操作(转载)
- 笔记整理--C语言
- 软件测试作业1 — 令我印象最深的BUG
- MMORPG战斗系统随笔(三)、AI系统简介
- AC的故事大结局山寨版(下)(最大流)
- JAVA加密技术-----MD5 与SHA 加密
- java.sql.SQLSyntaxErrorException: ORA-00911: 无效字符
- python面向对象笔记
- Codeforces 920F - SUM and REPLACE
- Android_ 重写系统Crash处理类,保存Crash信息到SD卡 和 完美退出程序的方法
- SpringBoot框架的权限管理系统
- Qt的一些鲜为人知但是非常有用的小功能
热门文章
- web渗透之常见shell反弹姿势
- Python_列表(list)
- python学习笔记 | 递归思想
- docker cp 拷贝文件 和 进入容器
- CTFshow萌新赛-千字文
- [APUE] 进程环境
- Bitter.Core系列三:Bitter ORM NETCORE ORM 全网最粗暴简单易用高性能的 NETCore ORM 之 示例模型创建
- Vim中的swp文件,在vim非正常退出时,再次编辑会出问题
- Jenkins部署web项目到Tomcat(热部署)
- Python中,单引号,双引号,三引号的使用区别与原因