पायथन में सर्कुलर सबलिस्ट की अधिकतम राशि खोजने का कार्यक्रम

मान लीजिए कि हमारे पास संख्याओं की एक सूची है, अब संख्याओं की एक गोलाकार सूची पर विचार करें जहां अंकों की शुरुआत और अंत पड़ोसी हैं। हमें सर्कुलर सूची में एक गैर-रिक्त उप-सूची का अधिकतम योग ज्ञात करना है।

इसलिए, यदि इनपुट संख्या =[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 + num

  • max_sum :=max_sum और cur_max का अधिकतम

  • cur_min :=न्यूनतम संख्या और cur_min + num

  • min_sum :=न्यूनतम min_sum और cur_min

• अगर max_sum <=0, तो

  • वापसी max_sum

• 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