Pythonで合計が最大kの長方形の合計を見つけるプログラム

2d行列と別の値kがあるとすると、sum≤kであるarectangleの最大の合計を見つける必要があります。

したがって、入力が次のような場合

k =15の場合、出力は12になります。これは、長方形[5、7]を使用して、12の合計が15未満になるためです。

これを解決するには、次の手順に従います-

• n：=a

  の行数

• m：=a

  の列数

• ans：=inf

• 0からnの範囲のi1の場合、実行

  • 行：=サイズmのリストで、0で埋めます

  • i1からnの範囲のi2については、次のようにします

    • 0からmの範囲のjについては、次のようにします

      • row [j]：=row [j] + a [i2、j]

    • s：=新しいセット

    • sに0を挿入

    • 合計：=0

    • 0からmの範囲のjについては、次のようにします

      • 合計：=合計+行[j];

      • temp：=（sum − k）より大きいsのすべてのアイテムのリスト

      • tempのサイズが0より大きい場合、

        • u：=最低温度

        • ans：=ansの最大値と（sum − u）

      • 合計を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