C++ এ কার্ডগুলি থেকে আপনি সর্বাধিক পয়েন্ট পেতে পারেন

ধরুন একটি সারিতে সাজানো বেশ কয়েকটি কার্ড রয়েছে, প্রতিটি কার্ডে সংশ্লিষ্ট পয়েন্ট রয়েছে এবং এই পয়েন্টগুলিকে কার্ডপয়েন্ট বলে পূর্ণসংখ্যা অ্যারেতে দেওয়া হয়েছে। এক ধাপে, আমরা শুরু থেকে বা সারির শেষ থেকে একটি কার্ড নিতে পারি। আমাদের ঠিক k কার্ড নিতে হবে। চূড়ান্ত স্কোর হবে আমরা যে কার্ডগুলো নিয়েছি তার পয়েন্টের যোগফল। সুতরাং, যদি আমাদের পূর্ণসংখ্যা অ্যারে কার্ডপয়েন্ট এবং পূর্ণসংখ্যা 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
- pre1[i] :=pre1[i] + pre1[i - 1]
আরম্ভ করার জন্য i :=n - 2, যখন i>=0, আপডেট করুন (i 1 দ্বারা কম করুন), −
- 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 :=ret এর সর্বোচ্চ এবং (pre1[i] + pre2[j])
- i এবং j 1 দ্বারা হ্রাস করুন
ret :=সর্বোচ্চ ret এবং pre2[n - k]
রিটার্ন রিটার্ন

উদাহরণ

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

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