【算法题】最大矩阵和

  • A+
所属分类:JAVA


共计 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);
    }
}
  • 我的微信
  • 这是我的微信扫一扫
  • weinxin
  • 我的微信公众号
  • 我的微信公众号扫一扫
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: