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

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

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

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

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

तालिका :=एक नया नक्शा
उपसर्ग :=मान 0 के साथ आरंभ की गई एक नई सूची
नकारात्मक:=मान 0 के साथ आरंभ की गई एक नई सूची
प्रत्येक अनुक्रमणिका के लिए i और मान j अंकों में, करें
- यदि j तालिका में मौजूद नहीं है, तो
  - तालिका[j] :=एक नई जोड़ी (i, 0)
  - अन्यथा,
    - तालिका [जे, -1]:=मैं
  - उपसर्ग में एक नया तत्व जोड़ें जो उपसर्ग + j के अंतिम तत्व के बराबर हो
  - नकारात्मक के अंतिम तत्व की नकल करें
  - अगर j <0 , तो
    - नकारात्मक का अंतिम तत्व :=ऋणात्मक का अंतिम तत्व + j
उत्तर:=ऋणात्मक अनंत
तालिका के सभी मानों में प्रत्येक जोड़ी (i,j) के लिए, करें
- यदि j, 0 के समान नहीं है, तो
  - sm1 :=उपसर्ग[j+1] - उपसर्ग[i]
  - अगर j> i+1, तो
    - sm2 :=ऋणात्मक[j] - ऋणात्मक[i+1]
  - अन्यथा,
    - एसएम2:=0
  - उत्तर :=अधिकतम (उत्तर, sm1 - sm2)
वापसी उत्तर

उदाहरण

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

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]