সি++-এ kটি নন-ওভারল্যাপিং সাবলিস্টের সর্বোচ্চ যোগফল বের করা

সমস্যা বিবরণ

একটি সংখ্যার তালিকা nums এবং মান k দেওয়া আছে। kটি নন-ওভারল্যাপিং, নন-এম্পটি সাবলিস্ট বাছাই করতে হবে যাতে তাদের যোগফলের যোগফল সর্বোচ্চ হয়।

উদাহরণ: nums = [11,-1,2,1,6,-24,11,-9,6], k = 3 → আউটপুট 36। সাবলিস্ট: [11,-1,2,1,6] (১৯), [11] (১১), [6] (৬) → মোট ৩৬।

সমাধানের পদ্ধতি

ডাইনামিক প্রোগ্রামিং (২ স্টেট):

1. hi[i] = iটি সাবলিস্ট নির্বাচন করে সর্বোচ্চ যোগফল (সাবলিস্ট বন্ধ আছে)।
2. open[i] = iটি সাবলিস্ট নির্বাচন করে সর্বোচ্চ যোগফল (সাবলিস্ট খোলা আছে, বর্তমান উপাদান যোগ করা যাবে)।
3. প্রতিটি উপাদান num এর জন্য:
   • nopen[i] = max(open[i] + num, hi[i-1] + num)
   • hi[i] = max(hi[i], open[i])
4. hi[k] রিটার্ন করুন।

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int>& nums, int k) {
    int n = nums.size();
    if (n == 0 || k == 0) return 0;
    vector<int> hi(k+1, INT_MIN), open(k+1, INT_MIN);
    hi[0] = 0;
    for (int num : nums) {
        vector<int> nopen(k+1, INT_MIN);
        for (int i = 1; i <= k; ++i) {
            if (open[i] > INT_MIN) nopen[i] = open[i] + num;
            if (hi[i-1] > INT_MIN) nopen[i] = max(nopen[i], hi[i-1] + num);
        }
        open = move(nopen);
        for (int i = 1; i <= k; ++i) hi[i] = max(hi[i], open[i]);
    }
    return hi[k];
}

int main() {
    vector<int> v = {11, -1, 2, 1, 6, -24, 11, -9, 6};
    int k = 3;
    cout << solve(v, 3);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {11,-1,2,1,6,-24,11,-9,6}, 3

আউটপুট: 36