โปรแกรมหาผลรวมสี่เหลี่ยมผืนผ้าที่มีผลรวมไม่เกิน k ใน Python

คำอธิบายโจทย์

ให้เมทริกซ์ 2D และค่า k ต้องการหาผลรวมสูงสุดของสี่เหลี่ยมผืนผ้าใดๆ ที่มีผลรวม ≤ k

ตัวอย่าง

เมทริกซ์:

วิธีแก้ปัญหา

ใช้เทคนิค Prefix Sum 2D ร่วมกับ Binary Search / Ordered Set:

1. фиกซ์แถวบน (i1) และแถวล่าง (i2) คำนวณผลรวมแนวตั้งของแต่ละคอลัมน์ระหว่างสองแถว
2. ปัญหาลดรูปเป็น: หา subarray สูงสุดที่ผลรวม ≤ k ในอาเรย์ 1D
3. ใช้ prefix sum และ ordered set (หรือ sorted list) เพื่อหา prefix ที่น้อยที่สุดที่ ≥ (current_sum - k)

โค้ด Python

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)
                curr_sum = 0
                
                for j in range(m):
                    curr_sum += row[j]
                    # หาค่าใน s ที่ > (curr_sum - k)
                    temp = [e for e in s if e > (curr_sum - k)]
                    if temp:
                        u = min(temp)
                        ans = max(ans, curr_sum - u)
                    s.add(curr_sum)
        
        return ans

ob = Solution()
matrix = [[5, -2], [7, 10]]
k = 15
print(ob.solve(matrix, k))

อินพุต

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

เอาต์พุต

12