首页 > 代码库 > 和最大连续子串续——和最大连续子矩阵
和最大连续子串续——和最大连续子矩阵
继上一节学习了和最大连续子串，推广到和最大连续子矩阵，以二维为例，子矩阵是矩阵行和列的组合，参考：http://blog.sina.com.cn/s/blog_a782701501016636.html
代码如下：
package programming;/**最大和的连续子矩阵 * 将连续子矩阵看做是一维连续子串，然后利用和最大连续子串方法，求出连续子串，进而求出子矩阵 * @author ywf * */public class MaxSumSubMatrix { /** * @param args */ public static void main(String[] args) { int[][] A = {{0, -2, -7, 0}, {9 , 2 , -6, 2}, {-4 , 1 ,-4 , 1}, {-1 , 8 , 0 ,-2}}; int[] temp = new int[A[0].length]; int subMaxSum = Integer.MIN_VALUE; int colStart = -1; int colEnd = -1; int rowStart = -1; int rowEnd = -1; //矩阵压缩 for(int i = 0 ;i<A.length;i++){ for(int j = i;j<A[i].length;j++){ for(int h = i;h<=j;h++){ for(int k = 0;k<temp.length;k++){ temp[k] += A[h][k]; } } int[] tempMax = getResult4(temp); if(tempMax[2]>subMaxSum){ subMaxSum = tempMax[2]; colStart = tempMax[0]; colEnd = tempMax[1]; rowStart = i; rowEnd = j; } temp = new int[A[0].length]; } } //输出和最大子矩阵 for(int i = rowStart;i<=rowEnd;i++){ for(int j = colStart;j<=colEnd;j++){ System.out.print(A[i][j]+" "); } System.out.println(); } System.out.println("sum:"+subMaxSum); } public static int[] getResult4(int[] array) { int[] result = new int[3]; int rmax = Integer.MIN_VALUE;//当前最大的和 int sum = Integer.MIN_VALUE;//当前的和 int start = -1;//最大子串的起始下标 int end = -1;//最大子串的结束下标 for (int i = 0; i < array.length; i++) { if (sum > 0) { sum += array[i]; } else { sum = array[i]; if(sum>rmax){ start = i; } } if (sum > rmax) { rmax = sum; end = i; } } result[0] = start; result[1] =end ; result[2] = rmax; return result; }}
和最大连续子串续——和最大连续子矩阵
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。