โปรแกรมหาผลรวมของสี่เหลี่ยมที่มีผลรวมสูงสุด k ใน Python

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

ดังนั้นหากอินพุตเป็นแบบ

5	−2
7	10

และ k =15 ผลลัพธ์จะเป็น 12 เนื่องจากเราสามารถหาสี่เหลี่ยมผืนผ้า [5, 7] เพื่อให้ได้ผลรวม 12 น้อยกว่า 15

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

n :=จำนวนแถวของ a
m :=จำนวนคอลัมน์ของ a
ตอบ :=inf
สำหรับ i1 ในช่วง 0 ถึง n ให้ทำ
- row :=รายการขนาด m และเติม 0
- สำหรับ i2 ในช่วง i1 ถึง n ให้ทำ
  - สำหรับ j ในช่วง 0 ถึง m ให้ทำ
    - row[j] :=row[j] + a[i2, j]
  - s :=ชุดใหม่
  - ใส่ 0 ลงใน s
  - ผลรวม :=0
  - สำหรับ j ในช่วง 0 ถึง m ให้ทำ
    - sum :=sum + row[j];
    - temp :=รายการสำหรับรายการทั้งหมดใน s ซึ่งมากกว่า (sum − k)
    - ถ้าขนาดของอุณหภูมิ> 0 แล้ว
      - u :=อุณหภูมิต่ำสุด
      - ans :=สูงสุดของ ans และ (ผลรวม − u)
    - ใส่ผลรวมลงใน s
กลับมาอีกครั้ง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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