Chương trình tìm tổng của hình chữ nhật có tổng nhiều nhất là k trong Python

Giả sử chúng ta có một ma trận 2d và một giá trị khác k, chúng ta phải tìm tổng lớn nhất của hình tam giác có tổng ≤ k.

Vì vậy, nếu đầu vào giống như

và k =15, thì đầu ra sẽ là 12, vì chúng ta có thể lấy hình chữ nhật [5, 7] để có tổng của 12 nhỏ hơn 15.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=số hàng của một

• m:=số cột của một

• ans:=inf

• đối với i1 trong phạm vi từ 0 đến n, thực hiện

  • row:=danh sách kích thước m và điền bằng 0

  • đối với i2 trong phạm vi i1 đến n, thực hiện

    • đối với j trong phạm vi từ 0 đến m, thực hiện

      • row [j]:=row [j] + a [i2, j]

    • s:=một tập hợp mới

    • chèn 0 vào s

    • tổng:=0

    • đối với j trong phạm vi từ 0 đến m, thực hiện

      • sum:=sum + row [j];

      • temp:=danh sách cho tất cả các mục trong s lớn hơn (sum - k)

      • nếu kích thước của nhiệt độ> 0, thì

        • u:=nhiệt độ tối thiểu

        • ans:=tối đa ans và (sum - u)

      • chèn tổng vào s

• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

[
[5, −2],
[7, 10]
], 15

Đầu ra

12