โปรแกรมค้นหาผลรวมของ k รายการย่อยที่ไม่ทับซ้อนกันซึ่งผลรวมสูงสุดใน C++

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า 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
• กำหนดอาร์เรย์ hi ขนาด k + 1 และเติมด้วย -inf
• กำหนดอาร์เรย์อื่นที่เปิดขนาด k + 1 และเติมด้วย -inf
• สวัสดี[0] :=0
• สำหรับแต่ละ num เป็น nums −
  • กำหนดอาร์เรย์ nopen ขนาด k + 1 และเติมด้วย -inf
  • สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=k อัปเดต (เพิ่ม i ขึ้น 1) ทำ
    • ถ้า open[i]> -inf แล้ว −
      • nopen[i] :=open[i] + num
    • ถ้า hi[i - 1]> -inf แล้ว −
      • nopen[i] :=สูงสุดของ nopen[i] และ hi[i - 1] + num
  • เปิด :=ย้าย(ไม่เปิด)
  • สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=k อัปเดต (เพิ่ม i ขึ้น 1) ทำ
    • 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

ผลลัพธ์

36