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

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

nums के शुरुआत या अंत से एक मान x चुनें।
स्कोर में multipliers[i] * x जोड़ें।
nums सरणी से x को हटाएं।

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

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

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

n := nums का आकार, m := multipliers का आकार
dp := m x (m+1) आकार का एक 2D सरणी जिसे 0 से भरा गया हो
i को m - 1 से 0 तक उल्टे क्रम में, करें
- j को i से m - 1 तक के लिए, करें
  - k := i + m - j - 1
  - dp[i, j] = (nums[i] * multipliers[k] + dp[i+1, j]) और (nums[j-m+n] * multipliers[k] + dp[i, j-1]) का अधिकतम
dp[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]