পাইথনে সার্কুলার সাবলিস্টের সর্বাধিক যোগফল খুঁজে বের করার প্রোগ্রাম

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

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[2, 3, -7, 4, 5], তাহলে আউটপুট 14 হবে, যেমন আমরা সাবলিস্ট [4, 5, 2, 3] নিতে পারি যার যোগফল 14।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• max_sum :=ঋণাত্মক অসীম, cur_max :=0

• min_sum :=পজিটিভ ইনফিনিটি, cur_min :=0

• প্রতিটি সংখ্যার জন্য, করুন

  • cur_max :=সংখ্যার সর্বোচ্চ এবং cur_max + সংখ্যা

  • max_sum :=সর্বাধিক_sum এবং cur_max

  • cur_min :=ন্যূনতম সংখ্যা এবং cur_min + সংখ্যা

  • min_sum :=সর্বনিম্ন min_sum এবং cur_min

• যদি সর্বোচ্চ_সমষ্টি <=0 হয়, তাহলে

  • সর্বোচ্চ_সমষ্টি ফেরত দিন

• max_sum এর সর্বাধিক ফেরত দিন এবং (সংখ্যায় সমস্ত উপাদানের যোগফল - 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