C++에서 합이 최대인 k개의 겹치지 않는 하위 목록의 합을 찾는 프로그램

<시간/>

nums라고 하는 숫자 목록과 다른 값 k가 있다고 가정하면, 합이 최대가 되도록 겹치지 않고 비어 있지 않은 하위 목록 k를 찾아야 합니다. k는 nums의 크기보다 작거나 같다고 생각할 수 있습니다.

따라서 입력이 nums =[11, -1, 2, 1, 6, -24, 11, -9, 6] k =3과 같으면 하위 목록을 선택할 수 있으므로 출력은 36이 됩니다. , -1, 2, 1, 6], [11], [6] [19, 11, 6] =36의 합을 구합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=숫자 크기
n이 0과 같거나 k가 0과 같으면 -
- 0을 반환
k + 1 크기의 배열 hi를 정의하고 -inf로 채움,
크기가 k + 1인 다른 배열을 정의하고 -inf로 채웁니다.
안녕[0] :=0
nums의 각 num에 대해 −
- k + 1 크기의 배열 noopen을 정의하고 -inf로 채움
- i를 초기화하려면:=1, i <=k일 때 업데이트(i를 1만큼 증가), do
  - 열린 경우[i]> -inf이면 -
    - 열지 않음[i] :=열림[i] + 숫자
  - hi[i - 1]> -inf이면 -
    - nopen[i] :=noopen[i] 및 hi[i - 1] + num의 최대값
- 열기 :=이동(열지 않음)
- i를 초기화하려면:=1, i <=k일 때 업데이트(i를 1만큼 증가), do
  - hi[i] :=hi[i] 및 open[i]의 최대값
안녕하세요[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