Given a 2D array, find the maximum sum subarray in it. For example, in the following 2D array, the maximum sum subarray is highlighted with blue rectangle and sum of this subarray is 29.
This problem is mainly an extension ofLargest Sum Contiguous Subarray for 1D array.
Thenaive solutionfor this problem is to check every possible rectangle in given 2D array. This solution requires 4 nested loops and time complexity of this solution would be O(n^4).
Kadane’s algorithmfor 1D array can be used to reduce the time complexity to O(n^3). The idea is to fix the left and right columns one by one and find the maximum sum contiguous rows for every left and right column pair. We basically find top
and bottom row numbers (which have maximum sum) for every fixed left and right column pair. To find the top and bottom row numbers, calculate sun of elements in every row from left to right and store these sums in an array say temp[]. So temp[i] indicates
sum of elements from left to right in row i. If we apply Kadane’s 1D algorithm on temp[], and get the maximum sum subarray of temp, this maximum sum would be the maximum possible sum with left and right as boundary columns. To get the overall maximum sum,
we compare this sum with the maximum sum so far.
用Kadane算法把原来O(n4)复杂度降低到O(n3)
package DP;
import java.util.Arrays;
public class MaxSumRectangleIn2DMatrix {
public static void main(String[] args) {
int[][] M = { {1, 2, -1, -4, -20},
{-8, -3, 4, 2, 1},
{3, 8, 10, 1, 3},
{-4, -1, 1, 7, -6}
};
findMaxSum(M);
}
// Time Complexity: O(n^3)
public static void findMaxSum(int[][] M){
int maxSum = Integer.MIN_VALUE;
int finalLeft = 0, finalRight = 0, finalTop = 0, finalBottom = 0;
int ROW = M.length, COL = M[0].length;
int[] temp = new int[ROW];
int[] startFinnish = {0, 0}; // [0]:start值,[1]:finnish值
// Set the left column
for(int left=0; left<COL; left++){ // 从左边开始的列号
Arrays.fill(temp, 0); // 每次重新开始计算时必须清空temp
// Set the right column for the left column set by outer loop
for(int right=left; right<COL; right++){ // 到右边结束的列号
// Calculate sum between current left and right for every row 'i'
for(int i=0; i<ROW; i++){ // 把当前检测的那“一列”放在temp数组中(temp[i] = M[i][right];)
temp[i] += M[i][right]; // 那“一列”随着右边结束行号的扩大而不断横向累加(temp[i] += M[i][right];)
}
// Find the maximum sum subarray in temp[]. The kadane() function
// also sets values of start and finish. So 'sum' is sum of
// rectangle between (start, left) and (finish, right) which is the
// maximum sum with boundary columns strictly as left and right.
int sum = kadane(temp, startFinnish, ROW); // 计算temp中的最大连续数组
// Compare sum with maximum sum so far. If sum is more, then update
// maxSum and other output values
if(sum > maxSum){ // 保存全局最优值
maxSum = sum;
finalLeft = left;
finalRight = right;
finalTop = startFinnish[0];
finalBottom = startFinnish[1];
}
}
}
System.out.format("(Top, Left) (%d, %d)\n", finalTop, finalLeft);
System.out.format("(Bottom, Right) (%d, %d)\n", finalBottom, finalRight);
System.out.format("Max sum is: %d\n", maxSum);
}
// Implementation of Kadane's algorithm for 1D array. The function returns the
// maximum sum and stores starting and ending indexes of the maximum sum subarray
// at addresses pointed by start and finish pointers respectively.
private static int kadane(int[] A, int[] startFinnish, int n) {
int sum = 0, maxSum = Integer.MIN_VALUE;
startFinnish[1] = -1; // Just some initial value to check for all negative values case
int localStart = 0;
for(int i=0; i<n; i++){
sum += A[i];
if(sum < 0){
sum =0;
localStart = i+1;
}else if(sum > maxSum){
maxSum = sum;
startFinnish[0] = localStart;
startFinnish[1] = i;
}
}
if(startFinnish[1] != -1){ // There is at-least one non-negative number
return maxSum;
}
maxSum = A[0]; // Special Case: When all numbers in arr[] are negative
startFinnish[0] = startFinnish[1] = 0;
for(int i=1; i<n; i++){ // Find the maximum element in array
if(A[i] > maxSum){
maxSum = A[i];
startFinnish[0] = startFinnish[1] = i;
}
}
return maxSum;
}
}
分享到:
相关推荐
1.建立一个形状类Shape作为基类,派生出圆类Circle和矩形类Rectangle,求出面积并获取相关信息。 具体要求如下: (1)形状类Shape (a)保护数据成员 double x,y:对于不同的形状,x和y表示不同的含义,如对于圆,...
LeetCode题目Largest Rectangle in Histogram 解答
定义一个名为rectangle 的矩形类,其属性数据为矩形左上角和右上角的点的坐标能计算矩形的面积
Matrix 4x4浮点矩阵,可以存储平移、比例和旋转信息 Matrix2D 2D矩阵类及常用方法 Rectangle 矩形类 Vector2 二维向量类 包含一些常用向量方法 EasySave h5缓存类 Debug 提供打印彩色日志,获取当前平台信息 Functor ...
function optseg = CSP2d_rectangle a=203; b=114.5; L=2799 ; W=1500; l=2*a; w=2*b; % L=4000; % W=1500; % l=215; % w=154; % L=10.1; % W=6.2; % l=2.1; % w=1.2; blnk=16; nmax=100; crcn=5; WL=[L 0]; % % %...
按以下描述和要求建立两个类:基类 Rectangle(矩形类) 和派生类 Cube(正方体) 1. Rectangle 私有成员: double x1, y1; //左下角的坐标 double x2, y2; //右上角的坐标 公有成员: 带缺省值的构造...
java 实验 继承与多态rectAngle 定义矩形类,用户输入矩形的长与宽,程序计算其面积和周长;派生子类正方形类,定义一个接口Printable源代码
实现利用Rectangle输出一个矩形的周长和面积
用于检测圆形和矩形之间碰撞的轻量级js库(2d) 用法 // Creates a new Rectangle at (0, 0) with (100x100) dimensions. var myRect = new Crash2D.Rect(0, 0, 100, 100); // Creates a new Circle at (50, 50) ...
C#-矩形-Rectangle
XNA Tutorial Collision Series 1 - 2D Rectangle Collision
程序举例-求矩阵之和 4-3 程序举例-求矩阵之和 任务需求 求一个3×3矩阵对角线元素之和 。 任务分析 利用双重for循环控制输入二维数组,再将a[i][i]累加后输出。 示例代码 main() { float a[3][3],sum=0; int i,j; ...
RoundRectangle2D.Float r2d=new RoundRectangle2D.Float(0, 0, btnWidth - 1, btnHeight - 1, 20, 20); Shape clip=g2d.getClip(); g2d.clip(r2d); GradientPaint paint = new GradientPaint(0.0F,0.0F,...
c++经典程序 北邮c++实验课老师留的作业
Hough算法检测矩形的长,并给出矩形的四个顶点坐标,极坐标中角度精度为1度。
2、定义抽象类Shape,抽象方法为showArea(),再定义矩形类Rectangle,正方形类Square,圆类 Circle,和各自的属性。定义主类、主方法,在main方法中构造3个对象,调用showArea方法;定义接口DiagArea,其中包含方法...
LintCode - 122. Largest Rectangle in Histogram(直方图最大矩形覆盖)(单调栈)题目链接题目解析主要是运用单调栈(单
本代码主要利用MATLAB工具实现MATLAB——使用rectangle命令创建二维矩形或椭圆区域,简单明了,易于理解
1,求直方图中最大矩形的面积。 上面是一个直方图,其中每个条的宽度为 1,给定高度 = [2,1,5,6,2,3]。 最大的矩形显示在阴影区域中,其面积 = 10 单位。 实现 1:O(n^2) class Solution { public int ...
已知的矩形类(Rectangle),现在希望增强它的功能,使得这个具有增强功能的矩形类能够拥有通过getCenter()获得Point和setCenter(intx,inty)的功能