首页 > 试题广场 >

最大子矩阵

[编程题]最大子矩阵

热度指数：17251 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。比如，如下4 * 4的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 的最大子矩阵是 9 2 -4 1 -1 8 这个子矩阵的大小是15。

输入描述:

输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。
再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。
已知矩阵中整数的范围都在[-127, 127]。

输出描述:

输出最大子矩阵的大小。

示例1

输入

输出

算法知识视频讲解

Java

嘿，man

import java.util.*;
public class Main{
    public static void main(String [] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int [][] matrix = new int[N][N];
        for(int i = 0;i<N;i++){
            for(int j = 0;j<N;j++){
                matrix[i][j] = in.nextInt();
            }
        }
        System.out.println(getMaxNum(matrix));
    }
    private static int getMaxNum(int[][] a) {
        int res = 0;
        if (a == null || a.length == 0 || a[0].length == 0) {
            return res;
        }
        int[] temp = null;
        res = Integer.MIN_VALUE;
        int max = 0;
        for (int i = 0; i < a.length; i++) {
            temp = new int[a[0].length];
            for (int j = i; j < a.length; j++) {
                max = 0;
                for (int k = 0; k < a[0].length; k++) {
                    temp[k] += a[j][k];
                    max = Math.max(max + temp[k], temp[k]);
                    res = Math.max(res,max);
                }
            }
        }

        return res;
    }
}

发表于 2020-01-26 22:32:43 回复(0)