二维最大子矩阵-洛谷P1719

原题复现

https://www.luogu.com.cn/problem/P1719

题目描述

为了更好地备战 NOIP 2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为：我们不光需要机房，我们还需要运动。于是她们决定找校长申请一块电脑组的课余运动场地。听说她们都是电脑组的高手，校长没有马上答应他们，而是先给她们出了一道数学题，并告诉她们，她们能获得的运动场地的面积就是她们能找到的这个最大的数字。

校长给她们一个大小为 $n\times n$ 的矩阵，矩阵中的每一个元素都有一个整数权值，要她们求出该矩阵中的最大加权矩形（即从中找一大小不限的矩形，使其中包含的所有元素的权值和最大）中所有元素的权值和，且矩阵中每个元素的权值均在区间 $[-127,127]$ 内。

几个女孩子有点犯难了，于是就找到了电脑组精打细算的 HZH,TZY 小朋友帮忙计算，但是遗憾的是，他们的答案都不一样。涉及土地的事情我们可不能含糊，你能帮忙计算出校长所给的矩形中加权和最大的矩形吗？

输入格式

第一行包含一个正整数 $n$ 。

接下来 $n$ 行每行包含 $n$ 个整数，表示给定的矩阵。

输出格式

输出一行一个整数，表示该矩阵的最大加权矩形中所有元素的权值和。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

样例解释

该矩阵中的最大加权矩形为

1
2
3

9  2
-4  1
-1  8

它们的和为 $15$ 。

数据范围

对于 $100\%$ 的数据， $1 \leq n\le 120$ 。

解题思路

首先介绍kadane算法,用于一维数组求最大子段和:

def kadane(arr):
    """求一维数组最大子段和"""
    max_sum = current = arr[0] #current记录到当前位置的最大子段和
    for i in arr[1:]:
        current = max(i , current + i) #更新到i位置时的子段和
        max_sum = max(max_sum,current)
    return max_sum

回到二维数组,找大最大子矩阵的核心是枚举上下边界并累加。
每个矩阵都有上边界和下边界,将所有上下边界可能的情况全部枚举,然后将二维数组转一维,一维数组的第k项对应二维数组第k列的和,找到一维数组中的最大子段,即可得到最大子矩阵。
二维转一维 –> 计算矩阵每一列的和
找一维最大子段 –> 每一列的和求最大和即是最大子矩阵

完整代码实现:

def kadane(arr):
    """求一维数组最大子段和"""
    max_sum = current = arr[0]
    for i in arr[1:]:
        current = max(i , current + i) #更新到i位置时的子段和
        max_sum = max(max_sum,current)
    return max_sum

n = int(input())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))

maxi = -float("inf")

for i in range(n):
    temp = [0]*n
    for j in range(i,n):
        for k in range(n):
            temp[k] += data[j][k]

        curr_max = kadane(temp)
        if curr_max > maxi:
            maxi = curr_max
print(maxi)

时间复杂度:O( $n^3$ )
轻松AC喵~