【算法题】最大矩阵和

共计 1061 个字符，预计需要花费 3 分钟才能阅读完成。

/**
 * 标题：最大矩阵和 | 时间限制：1秒 | 内存限制：262144K | 语言限制：不限
 * 给定一个二维整数矩阵，要在这个矩阵中选出一个子矩阵，使得这个子矩阵内所有的数字和尽量大，我们把这个子矩阵称为和最大子矩阵，子矩阵的选取原则是原矩阵中一块相互连续的矩形区域。
 * 输入的第一行包含2个整数n, m(1 <= n, m <= 10)，表示一个n行m列的矩阵，下面有n行，每行有m个整数，同一行中，每2个数字之间有1个空格，最后一个数字后面没有空格，所有的数字的在[-1000, 1000]之间。
 * 输出描述:
 * 输出一行一个数字，表示选出的和最大子矩阵内所有的数字和。
 * 示例1
 * 输入
 * 3 4
 * -3 5 -1 5
 * 2 4 -2 4
 * -1 3 -1 3
 * 输出
 * 20
 * 说明
 * 一个3*4的矩阵中，后面3列的子矩阵求和加起来等于20，和最大。
 */
public class M_N_T_32 {
    //这一题的思路是：由一维的连续子数组最大和，然后扩展到上下界的遍历，则可计算二维问题。//复杂度O(N^3)
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int rows = sc.nextInt();//行数
        int cols = sc.nextInt();//列数
        int res = Integer.MIN_VALUE;
        int[][] matrix = new int[rows][cols];
        for (int i = 0; i <= rows - 1; ++i) {
            for (int j = 0; j <= cols - 1; ++j) {
                matrix[i][j] = sc.nextInt();
            }
        }


        for (int begin = 0; begin <= rows - 1; ++begin) {//上边界
            int[] line = new int[cols];//每一列之和 //修改上边界之后，要清空重新开始
            for (int end = begin; end <= rows - 1; ++end) {//下边界
                //计算列元素和
                for (int j = 0; j <= cols - 1; ++j) {
                    line[j] += matrix[end][j];//下边界每向下一行，就计算更新下line[]数组的值
                }
                res = Math.max(res, line[0]);
                int sum = 0;
                for (int j = 0; j <= cols - 1; ++j) {
                    sum += line[j];
                    res = Math.max(res, sum);//取最大
                    if (sum < 0) sum = 0;//小于零，置零  //这样意味着最终的值可能是负数
                }
            }
        }
        System.out.println(res);
    }
}