สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums และจำนวนเต็ม k เราต้องหาผลรวมสูงสุดของลำดับย่อยที่ไม่ว่างของอาร์เรย์นั้น โดยที่สำหรับทุกๆ ตัวเลขสองตัวที่ต่อเนื่องกันในลำดับรองลงมา คือ nums[i] และ nums[j] โดยที่ i
ดังที่เราทราบกันดีอยู่แล้วว่าลำดับของอาร์เรย์นั้นได้มาจากการลบองค์ประกอบจำนวนหนึ่งออกจากอาร์เรย์ โดยปล่อยให้องค์ประกอบที่เหลืออยู่ในลำดับเดิม
ดังนั้น หากอินพุตเป็น [10,2,-9,5,19] และ k =2 เอาต์พุตจะเป็น 36 เนื่องจากลำดับรองลงมาคือ [10,2,5,19]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
ret :=-inf
กำหนดอาร์เรย์ dp และคัดลอกอาร์เรย์ที่กำหนดลงไป
กำหนดหนึ่ง deque dq
ใส่ v[0] ที่จุดเริ่มต้นของ dq
n :=ขนาดของวี
ret :=v[0]
สำหรับการเริ่มต้น i :=1 เมื่อฉัน
ถ้า i> k และองค์ประกอบแรกของ dq เหมือนกับ dp[i - k - 1] แล้ว
ลบองค์ประกอบด้านหน้าออกจาก dq
dp[i] :=สูงสุดของ dp[i] และ (ถ้า dq ว่างเปล่า ดังนั้น dp[i] + 0 มิฉะนั้น องค์ประกอบแรกของ dp + dq[i])
ในขณะที่ (ไม่ใช่ dq ว่างเปล่าและองค์ประกอบสุดท้ายของ dq
ลบองค์ประกอบสุดท้ายออกจาก dq
แทรก dp[i] ที่ส่วนท้ายของ dq
ret :=สูงสุดของ ret และ dp[i]
รีเทิร์น
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 10;
class Solution {
public:
int constrainedSubsetSum(vector<int>& v, int k) {
int ret = -inf;
vector<int> dp(v.begin(), v.end());
deque<int> dq;
dq.push_front(v[0]);
int n = v.size();
ret = v[0];
for (int i = 1; i < n; i++) {
if (i > k && dq.front() == dp[i - k - 1])
dq.pop_front();
dp[i] = max(dp[i], dq.empty() ? dp[i] + 0 : dp[i] +
dq.front());
while (!dq.empty() && dq.back() < dp[i])
dq.pop_back();
dq.push_back(dp[i]);
ret = max(ret, dp[i]);
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {10,2,-9,5,19};
cout << (ob.constrainedSubsetSum(v, 2));
} อินพุต
{10,2,-9,5,19}, 2 ผลลัพธ์
36
