পাইথনে একটি নির্দিষ্ট মানের চেয়ে ছোট বা সমান সর্বোচ্চ উপ-ম্যাট্রিক্স যোগফল বের করা

ধরুন, আমাদের কাছে একটি ২D ম্যাট্রিক্স এবং একটি মান k আছে। আমাদের এমন একটি উপ-ম্যাট্রিক্স (Rectangle) খুঁজে বের করতে হবে যার যোগফল k-এর চেয়ে ছোট বা সমান এবং সেই যোগফলটি সর্বোচ্চ হবে।

উদাহরণস্বরূপ, ম্যাট্রিক্স = [[5, -2], [7, 10]] এবং k = 15 হলে আউটপুট হবে 12, কারণ [5, 7] উপ-ম্যাট্রিক্সের যোগফল ১২ যা ১৫-এর চেয়ে কম।

সমাধানের ধাপসমূহ

n := সারির সংখ্যা, m := কলামের সংখ্যা
ans := -∞
প্রতিটি i1 (০ থেকে n-১) এর জন্য:
- row নামে m আকারের শূন্য-ভরা অ্যারে তৈরি করুন।
- প্রতিটি i2 (i1 থেকে n-১) এর জন্য:
  - প্রতিটি কলাম j এর জন্য row[j] += a[i2][j]
  - একটি সেট s তৈরি করুন এবং 0 যোগ করুন।
  - sum := 0
  - প্রতিটি j (০ থেকে m-১) এর জন্য:
    - sum += row[j]
    - s-তে (sum - k)-এর চেয়ে বড় সব উপাদান খুঁজুন।
    - যদি এমন উপাদান থাকে, তবে ন্যূনতমটি u হিসেবে নিন এবং ans := max(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