पायथन में 'वैध' सरणी का अधिकतम मान खोजने का प्रोग्राम

मान लीजिए हमारे पास n पूर्णांकों की एक सरणी 'nums' है। 'nums' में प्रत्येक मान उसकी 'शक्ति' दर्शाता है। सरणी 'वैध' मानी जाएगी यदि इसकी लंबाई दो से अधिक है और सरणी का पहला और अंतिम मान समान है। हमें सरणी से तत्वों को हटाकर इसे वैध बनाना है ताकि शेष तत्व शर्त को पूरा करें। आउटपुट के रूप में, हम सरणी के सभी शक्ति मानों को जोड़कर अधिकतम संभव शक्ति मान लौटाते हैं।

उदाहरण के लिए, यदि इनपुट nums = [3, 4, 5, 3, 4] है, तो आउटपुट 16 होगा।

यदि हम सरणी nums से पहला मान 3 हटा दें, तो यह [4, 5, 3, 4] बन जाती है। यह एक वैध सरणी है और शक्तियों का योग 4 + 5 + 3 + 4 = 16 है। यह दिए गए इनपुट से किसी भी वैध सरणी के लिए अधिकतम संभव योग है।

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

• table := एक नया मैप

• prefix := 0 से आरंभ एक नई सूची

• negative := 0 से आरंभ एक नई सूची

• nums में प्रत्येक इंडेक्स i और मान j के लिए:

  • यदि j table में मौजूद नहीं है, तो table[j] := (i, 0) का एक नया युग्म।

  • अन्यथा, table[j, -1] := i

  • prefix में एक नया तत्व जोड़ें जो prefix के अंतिम तत्व + j के बराबर हो।

  • negative के अंतिम तत्व को डुप्लिकेट करें।

  • यदि j < 0, तो negative का अंतिम तत्व := negative का अंतिम तत्व + j।

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

def solve(nums): table = {} prefix = [0] negative = [0] for i, j in enumerate(nums): if j not in table: table[j] = [i, 0] else: table[j][-1] = i prefix += prefix[-1] + j, negative += negative[-1], if j < 0: negative[-1] += j ans = float('-inf') for i,j in table.values(): if j != 0: sm1 = prefix[j+1] - prefix[i] sm2 = negative[j] - negative[i+1] if j > i+1 else 0 ans = max(ans, sm1 - sm2) return ans print(solve([3, 4, 5, 3, 4]))

इनपुट

[3, 4, 5, 3, 4] 

आउटपुट

16