โปรแกรมหาผลรวม subsequence สูงสุด ระยะห่างไม่ น้อยกว่า K (วิธี DP อีกแบบ) ใน C++

ให้อาร์เรย์ arr[] และ k หา subsequence ผลรวมมากที่สุด ที่สมาชิกห่างกันอย่างน้อย k ตำแหน่ง (DP อีกแบบ)

ตัวอย่าง: arr=[6,2,5,1,9,11,4], k=2 → 16 (เลือก 5 และ 11)

วิธีแก้ปัญหา (DP แบบ Forward)

dp[i] = ผลรวมสูงสุดของ subsequence ที่จบที่ i (ต้องเลือก arr[i]) ถ้า i < k: dp[i] = max(arr[i], dp[i-1]) มิฉะนั้น: dp[i] = max(arr[i], dp[i-k-1] + arr[i]) คำตอบ = max(dp[i]) ทุก i

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

int calcMaxSumSubSeq(int arr[], int k, int n) {
    vector dp(n);
    int maxSum = -1;
    dp[0] = arr[0];
    for (int i = 1; i < n; i++) {
        if (i < k)
            dp[i] = max(arr[i], dp[i-1]);
        else
            dp[i] = max(arr[i], dp[i-k-1] + arr[i]);
        maxSum = max(maxSum, dp[i]);
    }
    return maxSum;
}

int main() {
    int arr[] = {6,2,5,1,9,11,4};
    int n = 7, k = 2;
    cout << calcMaxSumSubSeq(arr, k, n); // 16
    return 0;
}

อินพุต

arr[] = {6,2,5,1,9,11,4}, k=2

เอาต์พุต

16