Chương trình tìm tổng hình chữ nhật lớn nhất không vượt quá k trong Python

Cho một ma trận 2D và một giá trị k, tìm tổng lớn nhất của một hình chữ nhật con sao cho tổng ≤ k.

Ví dụ, với ma trận:

và k = 15, đầu ra là 12 (hình chữ nhật [5, 7] cho tổng 12).

Giải pháp

Sử dụng kỹ thuật prefix sum kết hợp với tập hợp (set) để tìm hiệu số gần nhất:

• Duyệt qua tất cả cặp hàng (i1, i2), tính tổng cột giữa hai hàng này thành mảng 1D row
• Trên mảng row, tìm dãy con có tổng lớn nhất ≤ k bằng cách duy trì tập hợp các prefix sum
• Với mỗi prefix sum hiện tại sum, tìm giá trị nhỏ nhất trong set lớn hơn (sum - k)

Ví dụ minh họa

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_val = 0
                for j in range(m):
                    sum_val += row[j]
                    temp = [e for e in s if e > (sum_val - k)]
                    if len(temp) > 0:
                        u = min(temp)
                        ans = max(ans, sum_val - u)
                    s.add(sum_val)
        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