Python中寻找矩形和最大的程序

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

例如，如果输入是

5	−2
7	10

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

为了解决这个问题，我们将按如下步骤操作：

n：在a中的行数
m：在a中的列数
ans：inf
for i1 in range 0 to n，do
- row：大小为m的列表，填充为0
- for i2 in range i1 to n，do
  - for j in range 0 to m，do
  - row [j]：= row [j] + a [i2，j]
  - s：一个新的set
  - insert 0 into s
  - sum：0
  - for j in range 0 to m，do
  - sum：= sum + row [j]；
  - temp：s中所有大于（sum−k）的项的列表
  - 如果temp的大小> 0，则
    - u：temp的最小值
    - ans：ans和（sum−u）的最大值
  - insert sum into s
ans

让我们看看以下实现，以获得更好的理解

更多Python相关文章，请阅读：Python 教程

示例

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))