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

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

तो, अगर इनपुट पसंद है

5	−2
7	10

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

n :=एक की पंक्ति गणना
मी :=ए की कॉलम संख्या
Ans :=inf
i1 के लिए 0 से n की सीमा में, करें
- पंक्ति :=आकार m की सूची और 0 से भरें
- i2 के लिए i1 से n की श्रेणी में, करें
  - j के लिए 0 से m की सीमा में, करें
    - पंक्ति [जे]:=पंक्ति [जे] + ए [i2, जे]
  - s :=एक नया सेट
  - s में 0 डालें
  - योग :=0
  - j के लिए 0 से m की सीमा में, करें
    - योग :=योग + पंक्ति[j];
    - अस्थायी :=s में सभी मदों की एक सूची जो (योग - k) से बड़ी है
    - यदि तापमान का आकार> 0, तो
      - यू:=न्यूनतम तापमान
      - उत्तर :=अधिकतम उत्तर और (योग - यू)
    - एस में योग डालें
वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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