文档章节

求一个矩阵中最大的二维矩阵(元素和最大)

pczhangtl
 pczhangtl
发布于 2014/09/02 21:50
字数 276
阅读 68
收藏 0

求一个矩阵中最大的二维矩阵(元素和最大). :
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是
:
4 5
5 3
要求:(1)写出算法;(2)分析时间复杂度;(3)C写出关键代码

 

public class FindMax2DimensionMatrix {
	public static void main(String args[]) {
		int arr[] = { -1, 2, -3, -1, 20, -100, -34 };
		System.out.println(findOneDimensionMaxSum(arr));
		//1 2 0 3 4
//		2 3 4 5 1
//		1 1 5 3 0
		int matrix[][] = {{1,2,0,3,4}, {2,3,4,5,1}, {1,1,5,3,0}};
//		System.out.println(execute(matrix));
		System.out.println(findOneDimensionMaxSumWithStep(arr, 4));
	}

	public static int findOneDimensionMaxSumWithStep(int[] oneDMatrix, int step){
		int max = 0;
		int tmp = 0;
		for (int i = 0; i < oneDMatrix.length - (step - 1); i++) {
			for(int j = 0; j < step; j++){
			    tmp += 	oneDMatrix[i + j];
			}
			
			if (max < tmp) {
				max = tmp;
			} 
			
			tmp = 0;
		}
		
		return max;
	}
	
	public static int findOneDimensionMaxSum(int[] oneDMatrix) {
		int max = 0;
		int tmp = 0;
		for (int i = 0; i < oneDMatrix.length; i++) {
			tmp = tmp + oneDMatrix[i];
			if (max < tmp) {
				max = tmp;
			} else {
				if (tmp < 0) {
					tmp = 0;
				}
			}
		}

		return max;
	}

	public static int execute(int[][] matrix) {
		int finalMax = 0;
		int tmp = 0;
		int height = matrix.length;
		int width = matrix[0].length;
		for (int j = 0; j < width - 1; j++) {
			int max = 0;
			for (int i = 0; i < height; i++) {
                tmp = max + matrix[i][j] + matrix[i][j + 1];
                if(tmp > max){
                	max = tmp;
                }
                
                if(tmp < 0){
                	tmp = 0;
                }
			}
			
			if(finalMax < max){
				finalMax = max;
			}
		}
		
		return finalMax;
	}
}



© 著作权归作者所有

共有 人打赏支持
pczhangtl
粉丝 46
博文 707
码字总数 113318
作品 0
浦东
高级程序员
私信 提问
给定一个由整数组成二维矩阵(r*c),现在需要找出它的一个子矩阵,使得这个子矩阵内的所有元素之和最大,并把这个子矩阵称为最大子矩阵。

题目描述 有一个正整数和负整数组成的NxN矩阵,请编写代码找出元素总和最大的子矩阵。请尝试使用一个高效算法。 给定一个int矩阵mat和矩阵的阶数n,请返回元素总和最大的子矩阵的元素之和。保...

一贱书生
2016/11/29
120
0
算法知识梳理(5) - 数组第二部分

一、概要 本文介绍了有关数组的算法第一部分的代码实现,所有代码均可通过 在线编译器 直接运行,算法目录: 找到最小的个数 连续子数组的最大和 连续子数组的最大和(二维) 求数组当中的逆...

泽毛
2017/12/11
0
0
每日微软面试题——day 8(最大的二维子矩阵)

题:求一个矩阵中最大的二维子矩阵(元素和最大).如: 1 2 0 3 4 2 3 4 5 1 1 1 5 3 0 中最大的是: 4 5 5 3 要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码 分析:方法一、这是最容易...

zhanxinhang
2011/08/30
0
0
降维PCA

如有一组数组数据m个n维列向量Anxm 想要降维,随意丢弃数据显然不可取,降维可以降低程序计算复杂度,代价是丢弃了原始数据一些信息,那么降维的同时,又保留数据最多信息呢。 我们希望投影后...

14142135623731
2017/09/24
0
0
动态规划算法之:最长公共子序列 & 最长公共子串(LCS)

1、先科普下最长公共子序列 & 最长公共子串的区别: 找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。 2、最长公共子串 其实这是一个序贯决...

大数据之路
2013/03/25
0
2

没有更多内容

加载失败,请刷新页面

加载更多

高度可配置的 Linux 内存守护程序 Nohang!

部分功能特性 具有良好注释的配置文件,配置方面(配置中有 38 个参数) 可以将 SIGKILL 和 SIGTERM 作为发送给 victim 的信号 支持 zram(使用 mem_used_total 作为触发器) 可定制的监控强...

linuxCool
2分钟前
0
0
开源 java CMS - FreeCMS2.8 数据对象 unit

项目地址:http://www.freeteam.cn/ unit 在使用单位相关标签时,标签会封装unit供页面调用。 属性 说明 id id ismail 是否接收互动信件 name 名称 parid 父单位id isok 是否有效 ordernum 排...

freeteam
9分钟前
0
0
awk

awk awk 是一种编程语言,用于在linux/unix下对文本和数据进行处理。数据可以来自标准输入(stdin)、一个或多个文件,或其它命令的输出。它支持用户自定义函数和动态正则表达式等先进功能,是...

李超小牛子
20分钟前
0
0
扩展资源服务器解决oauth2 性能瓶颈

用户携带token 请求资源服务器 资源服务器拦截器 携带token 去认证服务器 调用tokenstore 对token 合法性校验 资源服务器拿到token,默认只会含有用户名信息 通过用户名调用userdetailsserv...

冷冷gg
52分钟前
18
0
[Git] Git整理(四) git rebase 的使用

概述 在之前总结分支相关内容时说道,合并两个分支的提交可以使用git merge,然而除了这种方式之外,还有一种方式就是使用git rebase,这两种方式的最终结果都相同,但是合并历史却不同;git...

天王盖地虎626
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部