मान लीजिए हमारे पास 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
