Python程序：查找矩形区域和不超过k的最大值

假设我们有一个二维矩阵和另一个值k，我们需要找到矩形区域的最大和，且该和不大于k。

例如，如果输入为：

并且k = 15，则输出将为12，因为我们可以选择矩形[5, 7]，其和为12，小于15。

为了解决这个问题，我们将遵循以下步骤：

• n := 矩阵a的行数

• m := 矩阵a的列数

• ans := 无穷大

• 对于 i1 从 0 到 n，执行：

  • row := 一个大小为m的列表，并用0填充

  • 对于 i2 从 i1 到 n，执行：

    • 对于 j 从 0 到 m，执行：

      • row[j] := row[j] + a[i2, j]

    • s := 一个新的集合

    • 将 0 插入到 s 中

    • sum := 0

    • 对于 j 从 0 到 m，执行：

      • sum := sum + row[j];

      • temp := 一个包含s中所有大于(sum − k)的元素的列表

      • 如果 temp 的大小 > 0，则：

        • u := temp 中的最小值

        • ans := ans 和 (sum − u) 中的最大值

      • 将 sum 插入到 s 中

• 返回 ans

让我们看下面的实现来更好地理解：

示例

 在线演示

class Solution:
   def solve(self, a, k):
      n = len(a)
      if n == 0:
         return 0;
      m = len(a[0])
      ans = -999999;
      for i1 in range(n):
         row = [0]*m;
         for i2 in range(i1, n):
            for j in range(m):
               row[j] += a[i2][j]
            s = set()
            s.add(0)
            sum = 0
            for j in range(m):
               sum += row[j];
               temp = [e for e in s if e > (sum − k)]
            if len(temp) > 0:
               u = min(temp)
               ans = max(ans, sum − u)
            s.add(sum)
         return ans
ob = Solution()
matrix = [
   [5, −2],
   [7, 10]
]
k = 15
print(ob.solve(matrix, k))

输入

[
[5, −2],
[7, 10]
], 15

输出

12

Arnab Chakraborty

更新于: 2020年12月26日

231 次查看

开启你的 职业生涯

通过完成课程获得认证

立即开始