程序查找在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