最大和子矩阵

[编程题]最大和子矩阵

热度指数：5813 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个NxN矩阵mat和矩阵的阶数n，已知矩阵由正整数和负整数组成，请返回元素总和最大的子矩阵的元素之和。要求元素绝对值小于等于100000，尽量高效且矩阵阶数小于等于200。

测试样例：

[[1,2,-3],[3,4,-5],[-5,-6,-7]],3

返回：10

算法知识视频讲解

Python

chace233

比较难想到的就是行累加后能够转变为一维数组求最大连续子数组和的问题。之后就是遍历所有行的组合就行了。

# -*- coding:utf-8 -*-
def find_max(arr):
    if arr is None or len(arr) == 0:
        return 0

    max_sum = cur_sum = float('-inf')
    for num in arr:
        if cur_sum <= 0:
            cur_sum = num
        else:
            cur_sum += num
        if cur_sum > max_sum:
            max_sum = cur_sum

    return max_sum

"""
对每一行，与下面行累加，得到一个一维数组，用一维数组求连续子数组的最大和的方式求出最大和。O(N^2)
"""
def find_max_matrix(matrix, n):
    if n <= 0:
        return 0
    max_sum = float('-inf')
    row = len(matrix)  # 行数
    for i in range(row):
        sum_arr = matrix[i]
        cur_sum = find_max(sum_arr)
        if cur_sum > max_sum:
            max_sum = cur_sum
        for j in range(i+1, row):
            sum_arr = [sum_arr[x]+matrix[j][x] for x in range(len(sum_arr))]
            cur_sum = find_max(sum_arr)
            if cur_sum > max_sum:
                max_sum = cur_sum
    return max_sum

class SubMatrix:
    def sumOfSubMatrix(self, mat, n):
        return find_max_matrix(mat, n)

发表于 2019-03-20 11:47:10 回复(0)