पायथन में k से कम या बराबर योग वाले आयत का अधिकतम योग ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास एक 2D मैट्रिक्स और एक अन्य मान k है, हमें उस आयत का सबसे बड़ा योग ज्ञात करना है जहां योग ≤ k हो।

इसलिए, यदि इनपुट इस प्रकार है:

5	-2
7	10

और k = 15, तो आउटपुट 12 होगा, क्योंकि हम आयत [5, 7] ले सकते हैं जिससे 15 से कम 12 का योग मिलता है।

हल करने के चरण

n := a की पंक्तियों की संख्या
m := a के स्तंभों की संख्या
ans := -infinity
i1 के लिए 0 से n तक की रेंज में, करें
- row := आकार m की सूची और 0 से भरें
- i2 के लिए i1 से n तक की रेंज में, करें
  - j के लिए 0 से m तक की रेंज में, करें
    - row[j] := row[j] + a[i2, j]
  - s := एक नया सेट
  - 0 को s में डालें
  - sum := 0
  - j के लिए 0 से m तक की रेंज में, करें
    - sum := sum + row[j]
    - temp := s में उन सभी आइटम्स की सूची जो (sum - k) से बड़े हैं
    - यदि temp का आकार > 0, तो
      - u := temp का न्यूनतम
      - ans := ans और (sum - u) का अधिकतम
    - sum को 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