পাইথনে সার্কুলার তালিকায় সর্বোচ্চ সাবলিস্ট সমষ্টি খুঁজে বের করার প্রোগ্রাম

ধরা যাক nums নামক একটি সংখ্যার তালিকা আছে, এখন nums-এর শুরু এবং শেষ প্রতিবেশী ধরে একটি সার্কুলার তালিকা বিবেচনা করুন। আমাদের এই সার্কুলার তালিকায় খালি নয় এমন সাবলিস্টের সর্বোচ্চ সমষ্টি খুঁজে বের করতে হবে।

উদাহরণ: nums = [2, 3, -7, 4, 5] হলে আউটপুট 14, কারণ [4, 5, 2, 3] সাবলিস্টের সমষ্টি 14।

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

• max_sum := -inf, cur_max := 0
• min_sum := +inf, cur_min := 0
• প্রতিটি num-এর জন্য nums-এ:
• cur_max := max(num, cur_max + num)
• max_sum := max(max_sum, cur_max)
• cur_min := min(num, cur_min + num)
• min_sum := min(min_sum, cur_min)
• যদি max_sum <= 0 হয়, max_sum ফেরত দিন।
• অন্যথায় max(max_sum, sum(nums) - min_sum) ফেরত দিন।

উদাহরণ কোড

import math
class Solution:
    def solve(self, nums):
        max_sum = -math.inf
        cur_max = 0
        min_sum = math.inf
        cur_min = 0
        for num in nums:
            cur_max = max(num, cur_max + num)
            max_sum = max(max_sum, cur_max)
            cur_min = min(num, cur_min + num)
            min_sum = min(min_sum, cur_min)
        if max_sum <= 0:
            return max_sum
        return max(max_sum, sum(nums) - min_sum)

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

ইনপুট

[2, 3, -7, 4, 5]

আউটপুট

14