Chương trình tìm tổng của k danh sách con không trùng lặp có tổng là lớn nhất trong C ++

Giả sử chúng ta có một danh sách các số gọi là num và một giá trị khác k, chúng ta phải tìm k danh sách con không trùng nhau, không rỗng sao cho tổng các tổng của chúng là lớn nhất. Chúng ta có thể coi k nhỏ hơn hoặc bằng kích thước của nums.

Vì vậy, nếu đầu vào là nums =[11, -1, 2, 1, 6, -24, 11, -9, 6] k =3, thì đầu ra sẽ là 36, vì chúng ta có thể chọn danh sách con [11 , -1, 2, 1, 6], [11] và [6] để nhận tổng là [19, 11, 6] =36.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của nums
• nếu n giống 0 hoặc k giống 0, thì -
  • trả về 0
• Xác định một mảng hi có kích thước k + 1 và điền bằng -inf,
• Xác định một mảng khác đang mở có kích thước k + 1 và điền bằng -inf
• xin chào [0]:=0
• cho mỗi num trong nums -
  • Xác định một nopen của mảng có kích thước k + 1 và điền bằng -inf
  • để khởi tạo i:=1, khi i <=k, cập nhật (tăng i lên 1), thực hiện
    • nếu mở [i]> -inf, thì -
      • nopen [i]:=open [i] + num
    • if hi [i - 1]> -inf, then -
      • nopen [i]:=tối đa là nopen [i] và hi [i - 1] + num
  • open:=move (nopen)
  • để khởi tạo i:=1, khi i <=k, cập nhật (tăng i lên 1), thực hiện
    • hi [i]:=tối đa là hi [i] và mở [i]
• trả lại xin chào [k]

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

{11, -1, 2, 1, 6, -24, 11, -9, 6}, 3

Đầu ra

36