【数据结构与算法】二维数组 最大矩形和

使用Kadane算法可以很方便地求解一维数组的最大连续子序列之和。

下面是Kadane算法的延伸，在二维数组中求解最大矩形。

思路是要利用一维数组的求解方法来求解二维，假设现在要求以i列开始到j列结束的最大和，不能是i和j之间的，必须以i和j是开始和结束。可以把i和j之间的列相加，最终得到一个一维数组，那么这个一维数组的最大值就是i和j的最大值，这是因为这个一维数组中存的就是每一行的和，与congi到j的矩形一一对应。

那么如何求i到j的最大值。即可以是i和j之间的。只需要遍历所有的i，j对，利用上面的方法求出所有的最大值，取其中的最大值。也就是说(i,i+1),(i,i+2).....,(i,j)， (i+1,i+2),....,(i+1,j)........。

时间复杂度，i，j对需要O(col*col)，每一次i，j对需要执行一次一维数组的Kadane，是O(row)的。因此总的是O(col*col*row)。

当然我们也可以以行的角度来看，那么就是O(col*row*row)。

这应该也算是一个优化，根据行数和列数的大小来决定以哪种视角来看。

代码：

	public int maxRecInMatrix(int[][] matrix){
		if(matrix == null || matrix.length == 0) return 0;
		int[] cash = new int[matrix.length];
		int left = 0, right = 0, up = 0, down = 0, max_maxtrix = matrix[0][0];
		for(int i = 0; i < matrix[0].length; i++){
			Arrays.fill(cash, 0);
			for(int j = i; j < matrix[0].length; j++){
				//add col to cash
				for(int k = 0; k < matrix.length; k++){
					cash[k] += matrix[k][j];
				}
				int cur_max = 0, max_array = cash[0], up_local = 0, down_local = 0, cur_up = 0, cur_down = 0;
				for(int k = 0; k < cash.length; k++){
					if(cash[k] > cur_max + cash[k]){
						cur_up = k;
						cur_down = k;
						cur_max = cash[k];
					}else{
						cur_down = k;
						cur_max = cur_max + cash[k];
					}
					if(cur_max > max_array){
						max_array = cur_max;
						up_local = cur_up;
						down_local = cur_down;
					}
				}
				if(max_array > max_maxtrix){
					max_maxtrix = max_array;
					up = up_local;
					down = down_local;
					left = i;
					right = j;
				}
			}
		}
		System.out.println("left:" + left+" right:"+right+" up:"+up +" down" + down);
		return max_maxtrix;
	}

	public static void main(String[] args) {
		Solution solution = new Solution();
		int[] nums = {4,8,10,240};
		int[][] matrix = {{2,1,-3,-4,5},{0,6,3,4,1},{2,-2,-1,4,-5},{-3,3,1,0,3}};
		//System.out.println(solution.findMinInsertions("a"));
		System.out.println(solution.maxRecInMatrix(matrix));
	}