मान लीजिए कई कार्ड एक पंक्ति में व्यवस्थित हैं, प्रत्येक कार्ड से जुड़े पॉइंट्स हैं, और ये पॉइंट्स cardPoints नामक इंटीजर ऐरे में दिए गए हैं। एक स्टेप में, हम पंक्ति के शुरुआत या अंत से एक कार्ड ले सकते हैं। हमें ठीक k कार्ड लेने हैं। अंतिम स्कोर हमारे द्वारा लिए गए कार्डों के पॉइंट्स का योग होगा। इसलिए, यदि हमारे पास इंटीजर ऐरे cardPoints और इंटीजर k है, तो अधिकतम स्कोर ढूंढें जो हम प्राप्त कर सकते हैं।
इसलिए, यदि इनपुट है cardPoints = [1,2,3,4,5,6,1], k = 3, तो आउटपुट 12 होगा, क्योंकि प्रारंभिक स्टेप के बाद, हमारा स्कोर हमेशा 1 होगा। अब, सबसे दायां कार्ड पहले चुनने से कुल स्कोर अधिकतम होगा। इष्टतम रणनीति दाईं ओर के तीन कार्ड लेने की है, जिससे अंतिम स्कोर 1 + 6 + 5 = 12 होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
दो ऐरे pre1 और prev2 परिभाषित करें और उन्हें v से इनिशियलाइज़ करें
ret := 0
n := v का आकार
i := 1 से शुरू करें, जब i < n, i बढ़ाते हुए, करें -
pre1[i] := pre1[i] + pre1[i - 1]
i := n - 2 से शुरू करें, जब i >= 0, i घटाते हुए, करें -
pre2[i] := pre2[i] + pre2[i + 1]
यदि k >= n, तो -
pre1[n - 1] लौटाएं
i := k - 1
ret := pre1[i]
(i को 1 से घटाएं)
j := n - 1
जब i >= 0, करें -
ret := max(ret, pre1[i] + pre2[j])
i और j को 1 से घटाएं
ret := max(ret, pre2[n - k])
ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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}आउटपुट
12
