পাইথনে সংখ্যা মুছে যাতে সর্বোচ্চ অ্যাডিটিভ স্কোর পাওয়া যায় সেটি বের করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে একটি সংখ্যার তালিকা nums আছে। একটি অপারেশন বিবেচনা করুন যেখানে আমরা একটি সংখ্যা বেছে নিই, সেটি মুছে ফেলি এবং আমাদের স্কোর বাড়ায় সেটির নিজস্ব মান এবং তার দুটি সংলগ্ন সংখ্যার যোগফল দিয়ে। আমরা যতবার চাই ততবার এই অপারেশন করতে পারি যতক্ষণ না প্রথম ও শেষ সংখ্যাকে বেছে নেওয়া হয়। আমাদের কাজ হল সর্বোচ্চ সম্ভাব্য স্কোর বের করা।

উদাহরণস্বরূপ, যদি ইনপুট হয় nums = [2, 3, 4, 5, 6], তবে আউটপুট হবে 39, কারণ আমরা ৫ কে বেছে নিলে যোগফল হবে (4+5+6)=15, অ্যারে হবে [2, 3, 4, 6]। তারপর ৪ বেছে নিলে যোগফল (3+4+6)=13, অ্যারে [2, 3, 6]। তারপর ৩ বেছে নিলে যোগফল (2+3+6)=11। মোট স্কোর 15+13+11=39।

• n := len(nums)
• যদি n < 3 হয়, তবে 0 রিটার্ন করুন।
• আকার (n+1) x (n+1) এমন একটি ২ডি অ্যারে dp বানান।
• 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]
      • যদি curr > ans হয়, তবে ans := curr
    • ans := ans + nums[i-1] + nums[r-1]
    • dp[i][r] := ans
• dp[1][n] রিটার্ন করুন।

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

[2, 3, 4, 5, 6]

39