C++-এ কার্ড থেকে সর্বোচ্চ পয়েন্ট বের করা

এক সারি কার্ড আছে যাদের পয়েন্ট cardPoints অ্যারেতে দেওয়া আছে। প্রতিটি স্টেপে শুরু বা শেষ থেকে একটা কার্ড নিতে পারব। ঠিক k টি কার্ড নিতে হবে। সর্বোচ্চ পয়েন্ট বের করতে হবে।

ইনপুট: cardPoints = [1,2,3,4,5,6,1], k = 3 → আউটপুট: 12 (ডান পাশের ১, ৬, ৫ নিলে)

সমাধানের ধাপগুলো (প্রিফিক্স সাম):

দুটি প্রিফিক্স সাম অ্যারে pre1 (বাম থেকে) ও pre2 (ডান থেকে) বানাব
যদি k >= n হয়, সকল কার্ড নিব
i = k-1 থেকে ০ পর্যন্ত এবং j = n-1 থেকে কমিয়ে যাব
ret = max(pre1[i] + pre2[j]) ট্র্যাক করব
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;
    }
};

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