数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序：查找和最大的k个不相交子列表
假设我们有一个名为nums的数字列表，以及另一个值k，我们需要找到k个不相交的、非空的子列表，使得它们的和的总和最大。我们可以认为k小于或等于nums的大小。
因此，如果输入类似于nums = [11, -1, 2, 1, 6, -24, 11, -9, 6]，k = 3，则输出将为36，因为我们可以选择子列表[11, -1, 2, 1, 6]、[11]和[6]，得到和[19, 11, 6] = 36。
为了解决这个问题，我们将遵循以下步骤：
- n := nums的大小
- 如果n等于0或k等于0，则：
- 返回0
- 定义一个大小为k + 1的数组hi，并用-inf填充。
- 定义另一个大小为k + 1的数组open，并用-inf填充。
- hi[0] := 0
- 对于nums中的每个数字：
- 定义一个大小为k + 1的数组nopen，并用-inf填充。
- 从i := 1初始化，当i <= k时，更新（增加i）：
- 如果open[i] > -inf，则：
- nopen[i] := open[i] + num
- 如果hi[i - 1] > -inf，则：
- nopen[i] := nopen[i]和hi[i - 1] + num的最大值
- 如果open[i] > -inf，则：
- open := 移动(nopen)
- 从i := 1初始化，当i <= k时，更新（增加i）：
- hi[i] := hi[i]和open[i]的最大值
- 返回hi[k]
示例（C++）
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& nums, int k) {
int n = nums.size();
if (n == 0 || k == 0)
return 0;
vector<int> hi(k + 1, INT_MIN), open(k + 1, INT_MIN);
hi[0] = 0;
for (int num : nums) {
vector<int> nopen(k + 1, INT_MIN);
for (int i = 1; i <= k; ++i) {
if (open[i] > INT_MIN)
nopen[i] = open[i] + num;
if (hi[i - 1] > INT_MIN)
nopen[i] = max(nopen[i], hi[i - 1] + num);
}
open = move(nopen);
for (int i = 1; i <= k; ++i)
hi[i] = max(hi[i], open[i]);
}
return hi[k];
}
int main(){
vector<int> v = {11, -1, 2, 1, 6, -24, 11, -9, 6};
int k = 3;
cout << solve(v, 3);
}输入
{11, -1, 2, 1, 6, -24, 11, -9, 6}, 3输出
36
更新于： 2020年12月12日
156 次查看
广告