資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中從卡片中獲得的最大點數
假設有幾張卡片排成一行，每張卡片都有相關的點數，這些點數在名為 cardPoints 的整數陣列中給出。在一步中，我們可以從行的開頭或結尾取出一張卡片。我們必須取正好 k 張卡片。最終得分將是我們取出的卡片的點數之和。因此，如果我們有整數陣列 cardPoints 和整數 k，則找到我們可以獲得的最大得分。
因此，如果輸入類似於 cardPoints = [1,2,3,4,5,6,1]，k = 3，則輸出將為 12，因為在初始步驟之後，我們的分數將始終為 1。現在，首先選擇最右邊的卡片將使總分最大化。最佳策略是取右邊的三張卡片，最終得分是 1 + 6 + 5 = 12。
要解決此問題，我們將遵循以下步驟 -
定義兩個陣列 pre1 和 prev2 並用 v 初始化它們
ret := 0
n := v 的大小
對於初始化 i := 1，當 i < 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，則 -
返回 pre1[n - 1]
i := k - 1
ret := pre1[i]
（減少 i 1）
j := n - 1
當 i >= 0 時，執行 -
ret := ret 和 (pre1[i] + pre2[j]) 的最大值
減少 i 和 j 1
ret := ret 和 pre2[n - k] 的最大值
返回 ret
示例
讓我們看看以下實現以更好地理解 -
#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}輸出
12
更新於: 2020 年 11 月 17 日
254 次檢視
廣告