Điểm tối đa bạn có thể nhận được từ thẻ trong C ++

Giả sử có một số thẻ được sắp xếp thành một hàng, mỗi thẻ có các điểm liên quan và những điểm này được cho trong mảng số nguyên được gọi là cardPoints. Trong một bước, chúng ta có thể lấy một thẻ từ đầu hoặc từ cuối hàng. Chúng ta phải lấy đúng k thẻ. Điểm cuối cùng sẽ là tổng điểm của những lá bài mà chúng ta đã lấy được. Vì vậy, nếu chúng ta có cardPoints mảng số nguyên và số nguyên k, thì hãy tìm điểm tối đa mà chúng ta có thể nhận được.

Vì vậy, nếu đầu vào là cardPoints =[1,2,3,4,5,6,1], k =3, thì đầu ra sẽ là 12, như sau bước đầu tiên, điểm của chúng ta sẽ luôn là 1. Bây giờ , chọn thẻ ngoài cùng bên phải trước sẽ tối đa hóa tổng điểm. Chiến lược tối ưu là lấy ba thẻ bên phải, cho điểm cuối cùng là 1 + 6 + 5 =12.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định hai mảng trước1 và trước2 và khởi tạo chúng bằng v

• ret:=0

• n:=kích thước của v

• để khởi tạo i:=1, khi i

  • pre1 [i]:=pre1 [i] + pre1 [i - 1]

• để khởi tạo i:=n - 2, khi i> =0, cập nhật (giảm i đi 1), thực hiện -

  • pre2 [i]:=pre2 [i] + pre2 [i + 1]

• nếu k> =n, thì -

  • trả về pre1 [n - 1]

• i:=k - 1

• ret:=pre1 [i]

• (giảm i đi 1)

• j:=n - 1

• while i> =0, do -

  • ret:=tối đa ret và (pre1 [i] + pre2 [j])

  • giảm i và j đi 1

• ret:=tối đa trong số ret và pre2 [n - k]

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

{1,2,3,4,5,6,1}

Đầu ra

12