程序查找在Python中最大和为k的矩形的和

假设我们有一个二维矩阵和另一个值k，我们必须找到sum≤k的矩形的最大和。

所以，如果输入像

并且k = 15，则输出将为12，因为我们可以采用矩形[5，7]来得到小于15的12之和。

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

• n：= a的行数

• m：= a的列数

• ans：= inf

• 对于范围为0至n的i1，执行

• 对于0到m范围内的j，执行

• s：=一个新集合

• 将0插入s

• 和：= 0

• 对于0到m范围内的j，执行

• 行[j]：=行[j] + a [i2，j]

• u：=最低温度

• ans：= ans和（sum − u）的最大值

• sum：= sum + row [j];

• temp：= s中所有项目的列表，列表大于(sum-k)

• 如果temp的大小> 0，则

• 将sum插入s

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

• 对于i1到n范围内的i2，执行

• 返回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