一、前言
本系列的文章将解决求整数数组中最大子数组的和及其扩展问题
题目来源于此：现代程序设计 作业2
本文主要是正对该问题进行扩展，处理二维数组中的该问题
二、题目描述
处理二维数组： 我们要求二维数组的子数组必须是矩形的，求整数数组中最大子数组的和
如下图，运行结果是 28
这是一个比较大的数组的例子
三、构思
一开始我的想法就是列举每一个子数组，并求出他们每个块内的和，再求出最大值，但是如果二维数组很大的话，这种方法就会不可行，因为数据处理量太大了，而且要确定一个区域的话，要先确定其四个顶点，然后再用类似小学求面积的方法去求区域内面积。光是想到过程就觉得要写好多代码。。。于是这个方案被pass了（四重循环）
将二维转化为一维处理，当子矩阵的上下行确定时，把上下行中每一列的数据当作一个单元，确定左右列的过程就是求以列为单元的一维数组的子数组最大和的过程，这种方法大大提高了效率
四、代码实现
public class twoDimensionalArraySum { public static void main(String[] args) { //初始化数组 int[][] arr = {{5, 6, -3, 8, -9, 2}, {1, -12, 20, 0, -3, -5}, {-9, -7, -3, 6, 7, -1}}; //输出结果 System.out.println(Maxsum_2(arr)); while (true){} } //求二维数组最大值 public static int Maxsum_2(int[][] arr) { //初始化最大值 int maxumum = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { for (int j = i; j < arr.length; j++) { int sum = 0; //拆分，将每一行都定义为一个新一维数组 int[] newArray = new int[arr[0].length]; //将每一行的每个元素值都替换为其元素后累加的值 for (int w = 0; w < arr[0].length; w++) { sum = 0; for (int k = i; k <= j; k++) { sum = sum + arr[k][w]; } newArray[w] = sum; } //求最大值 if (Maxsum(n) > maxumum) maxumum = Maxsum(n); } } return maxumum; } //一维数组子数组最大计算公式 public static int Maxsum(int[] arr){ int maxSum = Integer.MIN_VALUE; int sum = 0; for (int i = 0; i < arr.length; ++i) { if (sum < 0) { sum = arr[i]; } else { sum += arr[i]; } if (sum > maxSum) { maxSum = sum; } } return maxSum; } }
五、反思
在写代码时，不能拿到题目就开始敲代码，要先想好解题思路再去写代码，否则会浪费大量的时间去写一个运行不成功的程序，并且就算程序能跑起来，由于没有考虑复杂度的问题，所以程序运行起来会很慢
六、小结
这个问题具有一定的难度，如果方法选取不当的话，就会使得程序运行的非常缓慢，代码也会很复杂，如果还要别的解法，欢迎各位读者提供思路
