คะแนนสูงสุดจากการหยิบการ์ดใน C++

สมมติว่ามีการ์ดเรียงเป็นแถว แต่ละใบมีคะแนน ในแต่ละขั้นตอนหยิบได้ 1 ใบจากขวาหรือซ้าย ต้องหยิบกี่ใบ k ใบ หาคะแนนสูงสุด

ตัวอย่าง: cardPoints = [1,2,3,4,5,6,1], k = 3 ผลลัพธ์ = 12 (หยิบ 3 ใบขวาสุด: 1+6+5)

วิธีแก้ปัญหา (Prefix Sum)

1. คำนวณ prefix sum จากซ้าย (pre1) และจากขวา (pre2)
2. ลองหยิบ i ใบจากซ้าย และ k-i ใบจากขวา สำหรับ i = 0..k
3. หาค่าสูงสุดของ pre1[i-1] + pre2[n-k+i]
4. เวลา O(n), พื้นที่ O(n)

ตัวอย่างโค้ด C++

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

ผลลัพธ์

12