अधिकतम अंक जो आप C++ में कार्ड से प्राप्त कर सकते हैं

मान लीजिए कि एक पंक्ति में कई कार्ड व्यवस्थित हैं, प्रत्येक कार्ड में संबद्ध बिंदु हैं, और ये बिंदु कार्डपॉइंट नामक पूर्णांक सरणी में दिए गए हैं। एक चरण में, हम एक कार्ड शुरुआत से या पंक्ति के अंत से ले सकते हैं। हमें बिल्कुल k कार्ड लेने हैं। अंतिम स्कोर हमारे द्वारा लिए गए कार्डों के अंकों का योग होगा। इसलिए, यदि हमारे पास पूर्णांक सरणी कार्डपॉइंट और पूर्णांक k है, तो अधिकतम स्कोर प्राप्त करें जो हम प्राप्त कर सकते हैं।

इसलिए, यदि इनपुट कार्डपॉइंट्स =[1,2,3,4,5,6,1], के =3 जैसा है, तो आउटपुट 12 होगा, क्योंकि प्रारंभिक चरण के बाद, हमारा स्कोर हमेशा 1 होगा। अब , सबसे पहले सबसे सही कार्ड चुनने से कुल स्कोर अधिकतम होगा। 1 + 6 + 5 =12 का अंतिम स्कोर देते हुए, तीन कार्डों को दाईं ओर ले जाना इष्टतम रणनीति है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

दो सरणियों को परिभाषित करें pre1 और prev2 और उन्हें v के साथ प्रारंभ करें
रिट:=0
n:=वी का आकार
इनिशियलाइज़ करने के लिए मैं :=1, जब i
- pre1[i] :=pre1[i] + pre1[i - 1]
इनिशियलाइज़ करने के लिए i :=n - 2, जब i>=0, अपडेट करें (i से 1 घटाएं), −
करें
- pre2[i] :=pre2[i] + pre2[i + 1]
यदि k>=n, तो −
- वापसी पूर्व1[n - 1]
मैं :=के - 1
रिट :=प्री1[i]
(i 1 से घटाएं)
जे:=एन - 1
जबकि मैं>=0, करते हैं -
- ret :=अधिकतम रिट और (pre1[i] + pre2[j])
- i और j को 1 से घटाएं
रिट :=अधिकतम रिट और प्री2[एन-के]
वापसी रिट

उदाहरण

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int maxScore(vector<int>& v, int k) {
      vector<int> pre1(v.begin(), v.end());
      vector<int> pre2(v.begin(), v.end());
      int ret = 0;
      int n = v.size();
      for (int i = 1; i < n; i++) {
         pre1[i] += pre1[i - 1];
      }
      for (int i = n - 2; i >= 0; i--) {
         pre2[i] += pre2[i + 1];
      }
      if (k >= n) {
         return pre1[n - 1];
      }
      int i = k - 1;
      ret = pre1[i];
      i--;
      int j = n - 1;
      while (i >= 0) {
         ret = max(ret, pre1[i] + pre2[j]);
         i--;
         j--;
      }
      ret = max(ret, pre2[n - k]);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5,6,1};
   cout << (ob.maxScore(v, 3));
}

इनपुट

{1,2,3,4,5,6,1}