पायथन में गुणन संचालन करने से अधिकतम अंक प्राप्त करने का कार्यक्रम

मान लीजिए कि हमारे पास क्रमशः n और m आकार के दो सरणियाँ संख्याएँ और गुणक हैं (n>=m)। सरणियाँ 1-अनुक्रमित हैं। अब हमारा प्रारंभिक स्कोर 0 है। हम ठीक एम ऑपरेशन करना चाहते हैं। Ith ऑपरेशन (1-अनुक्रमित) पर, हम करेंगे -

अंकों के प्रारंभ या अंत में से x में से एक मान चुनें।
गुणक [i] * x को स्कोर में जोड़ें।
सरणी अंकों से x निकालें।

हमें m ऑपरेशन करने के बाद अधिकतम स्कोर ज्ञात करना है।

इसलिए, यदि इनपुट संख्या =[5,10,15], गुणक =[5,3,2] की तरह है, तो आउटपुट 115 होगा क्योंकि हम 15 ले सकते हैं और 5 से गुणा करके 5*15 =75 प्राप्त कर सकते हैं। , तो 10*3 =30, तो कुल 75+30 =105 और अंत में 5*2 =10 है, इसलिए कुल 105+10 =115।

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

n :=अंकों का आकार, m :=आकार गुणक
dp :=m x (m+1) आकार की एक 2D सरणी और 0 से भरें
मैं के लिए सूची की सीमा 0 से m -1 के विपरीत है, करें
- j के लिए i से m-1 की श्रेणी में, करें
  - के :=मैं + एम - जे - 1
  - dp[i, j] =अधिकतम (अंक [i] * गुणक [k] + dp [i+1, j]) और (अंक [j-m+n] * गुणक [k] + dp [i, j -1])
डीपी का अंतिम तत्व लौटाएं [0]

उदाहरण

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

def solve(nums, multipliers):
   n, m = len(nums), len(multipliers)
   dp = [[0]*m for _ in range(m+1)]

   for i in reversed(range(m)):
      for j in range(i, m):
         k = i + m - j - 1
         dp[i][j] = max(nums[i] * multipliers[k] + dp[i+1][j], nums[j-m+n] * multipliers[k] + dp[i][j-1])

   return dp[0][-1]

nums = [5,10,15]
multipliers = [5,3,2]
print(solve(nums, multipliers))

इनपुट

[5,10,15], [5,3,2]