程序查找k个不重叠子列表的和，其总和在C ++中为最大

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个称为nums的数字列表，另一个值为k，我们必须找到k个非重叠，非空的子列表，以使它们的总和最大。我们可以认为k小于或等于nums的大小。

因此，如果输入像nums = [11，-1，2，1，1，6，-24，11，-9，6] k = 3，那么输出将是36，因为我们可以选择子列表[11 ，-1、2、1、6]，[11]和[6]得出[19、11、6] = 36的总和。

范例（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

以上是 程序查找k个不重叠子列表的和，其总和在C ++中为最大 的全部内容， 来源链接： utcz.com/z/321459.html