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 := 移动(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 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告