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
广告