首页 > 试题广场 >

最大子矩阵

[编程题]最大子矩阵

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

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是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

输入

输出

算法知识视频讲解

Python

卑微求offer的小菜鸡

def max_subarr_sum(arr):
    local_max = -float("inf")
    res = -float("inf")
    for num in arr:
        local_max = max(num, local_max + num)
        res = max(local_max, res)
    return res


def solve(matrix):
    m, n = len(matrix), len(matrix[0])
    res = -1
    for i in range(n):
        for j in range(i, n):
            arr = [sum(matrix[k][i:j + 1]) for k in range(m)]
            res = max(res, max_subarr_sum(arr))
    return res


if __name__ == '__main__':
    n = int(input())
    matrix = []
    while n:
        matrix.append(list(map(int, input().split())))
        n -= 1
    print(solve(matrix))

先求一维最大子序列，然后把双指针把矩阵压缩。

发表于 2020-09-22 02:19:41 回复(0)

Python

TimeMac

try:
    while True:
        num = int(input())
        matrix = []
        for i in range(num):
            matrix.append(list(map(int,input().split())))
        maxSubMatrix = 0
        for i in range(num):
            array = [0] * num           #i行到j行之间同列的相加
            for j in range(i,num):
                for q in range(num):    #j每次加一array都会继承前面的，只有i变化时才重置array
                    array[q] += matrix[j][q]
                temp = array[0]
                ans = array[0]
                for k in range(1,num):  #对之前得到的i行到j行同列中找最大连续和
                    temp= max(temp+array[k],array[k])
                    ans = max(temp,ans)
                if maxSubMatrix < ans:
                    maxSubMatrix = ans
        print(maxSubMatrix)
except Exception:
    pass

编辑于 2018-10-03 18:02:06 回复(1)