k নন-ওভারল্যাপিং সাবলিস্টের যোগফল খুঁজে বের করার প্রোগ্রাম যার যোগফল C++ এ সর্বাধিক

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

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[11, -1, 2, 1, 6, -24, 11, -9, 6] k =3, তাহলে আউটপুট হবে 36, যেমন আমরা সাবলিস্টগুলি নির্বাচন করতে পারি [11] , -1, 2, 1, 6], [11], এবং [6] যোগফল পেতে [19, 11, 6] =36।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n :=সংখ্যার আকার
যদি n 0 এর মত হয় বা k 0 এর মত হয়, তাহলে −
- রিটার্ন 0
k + 1 আকারের একটি অ্যারে হাই সংজ্ঞায়িত করুন এবং -inf দিয়ে পূরণ করুন,
k + 1 আকারের খোলা আরেকটি অ্যারে সংজ্ঞায়িত করুন এবং -inf দিয়ে পূরণ করুন
হাই[0] :=0
প্রতিটি সংখ্যার জন্য −
- k + 1 আকারের একটি অ্যারে নোপেন সংজ্ঞায়িত করুন এবং -inf দিয়ে পূরণ করুন
- আরম্ভ করার জন্য i :=1, যখন i <=k, আপডেট করুন (i 1 দ্বারা বাড়ান), করুন
  - যদি খোলা হয়[i]> -inf, তারপর −
    - nopen[i] :=open[i] + num
  - যদি hi[i - 1]> -inf হয়, তাহলে −
    - nopen[i] :=সর্বাধিক nopen[i] এবং hi[i - 1] + সংখ্যা
- খোলা :=সরানো(খালি)
- আরম্ভ করার জন্য i :=1, যখন i <=k, আপডেট করুন (i 1 দ্বারা বাড়ান), করুন
  - hi[i] :=সর্বাধিক হাই[i] এবং খুলুন[i]
রিটার্ন হাই[কে]

উদাহরণ (C++)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#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);
}

ইনপুট

{11, -1, 2, 1, 6, -24, 11, -9, 6}, 3