Python程式：查詢矩形區域和不超過k的最大值

假設我們有一個二維矩陣和另一個值k，我們需要找到矩形區域的最大和，且該和不大於k。

例如，如果輸入為：

5−2
710

並且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

更新於: 2020年12月26日

231 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告