คะแนนสูงสุดที่คุณจะได้รับจากการ์ดใน C++

สมมติว่ามีไพ่หลายใบเรียงกันเป็นแถว โดยไพ่แต่ละใบมีจุดที่เกี่ยวข้องกัน และจุดเหล่านี้จะถูกกำหนดในอาร์เรย์จำนวนเต็มที่เรียกว่า cardPoints ในขั้นตอนเดียว เราสามารถนำไพ่หนึ่งใบจากจุดเริ่มต้นหรือจุดสิ้นสุดของแถว เราต้องใช้ไพ่ k อย่างแน่นอน คะแนนสุดท้ายจะเป็นผลรวมของแต้มของไพ่ที่เราได้ไป ดังนั้น หากเรามี cardPoints อาร์เรย์จำนวนเต็มและจำนวนเต็ม k แล้ว จงหาคะแนนสูงสุดที่เราจะได้รับ

ดังนั้น ถ้าอินพุตเหมือน cardPoints =[1,2,3,4,5,6,1], k =3 ผลลัพธ์จะเป็น 12 เช่นเดียวกับขั้นตอนเริ่มต้น คะแนนของเราจะเป็น 1 เสมอ การเลือกไพ่ขวาสุดก่อนจะทำให้คะแนนรวมสูงสุด กลยุทธ์ที่ดีที่สุดคือหยิบไพ่สามใบทางด้านขวา ให้คะแนนสุดท้าย 1 + 6 + 5 =12

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดสองอาร์เรย์ pre1 และ prev2 และเริ่มต้นด้วย v
ยกเลิก :=0
n :=ขนาดของวี
สำหรับการเริ่มต้น i :=1 เมื่อฉัน
- pre1[i] :=pre1[i] + pre1[i - 1]
สำหรับการเริ่มต้น i :=n - 2 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -
- pre2[i] :=pre2[i] + pre2[i + 1]
ถ้า k>=n แล้ว −
- กลับก่อน1[n - 1]
ผม :=k - 1
ret :=pre1[i]
(ลด i โดย 1)
เจ :=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}