k गैर-अतिव्यापी उप-सूचियों का योग ज्ञात करने का कार्यक्रम, जिनका योग C++ में अधिकतम है

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है, और एक अन्य मूल्य k, हमें k गैर-अतिव्यापी, गैर-रिक्त उप-सूचियों को खोजना होगा जैसे कि उनके योग का योग अधिकतम हो। हम मान सकते हैं कि k, अंकों के आकार से छोटा या उसके बराबर है।

इसलिए, यदि इनपुट nums =[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
क + 1 आकार के हाय को परिभाषित करें और -inf से भरें,
k + 1 आकार के खुले हुए एक अन्य सरणी को परिभाषित करें और -inf से भरें
नमस्ते[0] :=0
अंकों में प्रत्येक अंक के लिए −
- k + 1 आकार की एक सरणी को परिभाषित करें और -inf से भरें
- इनिशियलाइज़ i :=1 के लिए, जब i <=k, अपडेट करें (i को 1 से बढ़ाएँ), करें
  - यदि खुला है[i]> -inf, तो −
    - नोपेन[i] :=open[i] + num
  - अगर hi[i - 1]> -inf, तो −
    - nopen[i] :=ज्यादा से ज्यादा noopen[i] और hi[i - 1] + num
- खुला:=चाल (नहीं खुला)
- इनिशियलाइज़ i :=1 के लिए, जब i <=k, अपडेट करें (i को 1 से बढ़ाएँ), करें
  - hi[i] :=अधिकतम hi[i] और खुला[i]
नमस्ते वापसी[k]

उदाहरण (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