数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告