पायथन में नंबर डिलीट करके अधिकतम एडिटिव स्कोर खोजने का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है। एक ऑपरेशन पर विचार करें जहां हम एक नंबर चुनते हैं, उसे हटाते हैं और अपना स्कोर उस नंबर और उसके दो आसन्न नंबरों के योग से बढ़ाते हैं। हम इस ऑपरेशन को जितनी बार चाहें कर सकते हैं जब तक हम लिस्ट के पहले या आखिरी नंबर को नहीं चुनते। हमें अधिकतम संभव स्कोर ढूंढना है।

उदाहरण के लिए, यदि इनपुट nums = [2, 3, 4, 5, 6] है, तो आउटपुट 39 होगा, क्योंकि हम 5 चुनते हैं, योग (4+5+6)=15, ऐरे [2,3,4,6], फिर 4 चुनते हैं, योग (3+4+6)=13, ऐरे [2,3,6], फिर 3 चुनते हैं, योग (2+3+6)=11, कुल 15+13+11=39।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (डायनामिक प्रोग्रामिंग):

n := len(nums)
यदि n < 3, तो 0 लौटाएं
dp एक 2D ऐरे आकार (n+1) x (n+1)
len := 3 से n तक:
- i := 1 से i+len-1 <= n तक:
  - r := i+len-1
  - ans := 0
  - k := i+1 से r-1 तक:
    - curr := dp[i][k] + dp[k][r] + nums[k-1]
    - ans = max(ans, curr)
  - ans += nums[i-1] + nums[r-1]
  - dp[i][r] := ans
dp[1][n] लौटाएं

उदाहरण कोड (C++ से पायथन में अनुवादित)

class Solution:
    def solve(self, nums):
        n = len(nums)
        if n < 3:
            return 0
        dp = [[0]*(n+1) for _ in range(n+1)]
        for length in range(3, n+1):
            for i in range(1, n-length+2):
                r = i + length - 1
                ans = 0
                for k in range(i+1, r):
                    curr = dp[i][k] + dp[k][r] + nums[k-1]
                    if curr > ans:
                        ans = curr
                ans += nums[i-1] + nums[r-1]
                dp[i][r] = ans
        return dp[1][n]

ob = Solution()
nums = [2, 3, 4, 5, 6]
print(ob.solve(nums))

इनपुट

[2, 3, 4, 5, 6]