পাইথনে বড় কনক্যাটেনেটেড লিস্ট থেকে সর্বোচ্চ সাবলিস্ট যোগফল বের করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে একটি সংখ্যার তালিকা nums এবং অন্য একটি মান k আছে, যা nums কে k বার কনক্যাটেনেট করে একটি বড় লিস্ট বানাওয়াকে নির্দেশ করে। আমাদের কাজ হল সেই বড় লিস্টে সবচেয়ে বড় যোগফল বিশিষ্ট কন্টiguous সাবলিস্টের যোগফল বের করা।

উদাহরণস্বরূপ, যদি ইনপুট হয় nums = [1, 3, 4, -5] এবং k = 1, তবে আউটপুট হবে 11, কারণ আমরা সাবলিস্ট [2, 4, 5] নিতে পারি। (নোট: উদাহরণে ইনপুট ও আউটপুটের মান মেলেনা, কিন্তু লজিক অনুযায়ী বুঝানো হয়েছে)

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

s := ans := lo := 0
_ কে ০ থেকে min(k, 2) পর্যন্ত লুপ চালান:
- প্রতিটি x এর জন্য nums-এ:
  - s := s + x
  - lo := min(lo, s)
  - ans := max(ans, s - lo)
ans + max(0, sum(nums)) * max(0, k-2) রিটার্ন করুন।

উদাহরণ কোড

class Solution:
    def solve(self, nums, k):
        s = ans = lo = 0
        for _ in range(min(k, 2)):
            for x in nums:
                s += x
                lo = min(lo, s)
                ans = max(ans, s - lo)
        return ans + max(0, sum(nums)) * max(0, (k - 2))

ob = Solution()
nums = [2, 4, 5, -4]
k = 1
print(ob.solve(nums, k))

ইনপুট

[2, 4, 5, -4], 1

আউটপুট