पायथन में संख्याओं को हटाकर अधिकतम योगात्मक अंक प्राप्त करने का कार्यक्रम

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

इसलिए, यदि इनपुट संख्या =[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 :=अंकों का आकार
अगर n <3, तो:
- आकार की एक 2D सरणी परिभाषित करें (n + 1) x (n + 1)
इनिशियलाइज़ लेन के लिए:=3, जब लेन <=n, अपडेट करें (लेन को 1 से बढ़ाएँ), करें -
- इनिशियलाइज़ i :=1 के लिए, जब i + len - 1 <=n, अपडेट करें (i को 1 से बढ़ाएँ), −
  - r :=i + len - 1
  - उत्तर:=0
  - इनिशियलाइज़ k :=i + 1 के लिए, जब k <=r-1, अपडेट करें (k को 1 से बढ़ाएँ), −
    - curr:=dp[i, k] + dp[k, r] + nums[k - 1]
    - अगर curr> ans, तो:
  - उत्तर :=उत्तर + अंक[i - 1] + अंक [r - 1]
  - dp[i, r] :=ans
रिटर्न डीपी[1, एन]

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& nums) {
      int n = nums.size();
      if (n < 3) return 0;
         vector<vector<int>> dp(n + 1, vector<int>(n + 1));
         for (int len = 3;
            len <= n; ++len) {
               for (int i = 1; i + len - 1 <= n; ++i) {
                  int r = i + len - 1;
                  int ans = 0;
               for (int k = i + 1; k <= r - 1; ++k) {
                  int 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];
   }
};
int solve(vector<int>& nums) {
   return (new Solution())->solve(nums);
}
main(){
   vector<int> v = {2, 3, 4, 5, 6};
   cout << solve(v);
}

इनपुट

[2, 3, 4, 5, 6]