假设我们有一个称为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的总和。
让我们看下面的实现以更好地理解-
#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