Điểm tối đa từ chọn thẻ bài (Maximum Points You Can Obtain from Cards) trong C++

Cho mảng cardPoints điểm các thẻ bài xếp hàng. Mỗi bước lấy 1 thẻ từ đầu hoặc cuối. Phải lấy đúng k thẻ. Tìm tổng điểm lớn nhất.

Ví dụ

Đầu vào: cardPoints = [1,2,3,4,5,6,1], k = 3
Đầu ra: 12 (lấy 3 thẻ cuối: 1+6+5).

Thuật toán tiền tố + hậu tố

Tương đương: chọn i thẻ từ đầu và k-i thẻ từ cuối (0 ≤ i ≤ k). Tính tổng tiền tố pre[i] và hậu tố suf[i], tìm max pre[i] + suf[k-i].

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxScore(vector& v, int k) {
        int n = v.size();
        vector pre(n+1), suf(n+1);
        for (int i = 0; i < n; ++i) pre[i+1] = pre[i] + v[i];
        for (int i = n-1; i >= 0; --i) suf[i] = suf[i+1] + v[i];
        int ans = 0;
        for (int i = 0; i <= k; ++i)
            ans = max(ans, pre[i] + suf[n - (k - i)]);
        return ans;
    }
};

Độ phức tạp

• Thời gian: O(N) - tính prefix/suffix và duyệt k.
• Không gian: O(N) - mảng tiền tố/hậu tố (có thể O(1) nếu chỉ dùng biến).

Kết quả kiểm thử

Đầu vào: {1,2,3,4,5,6,1}, 3
Đầu ra: 12