โปรแกรมหาผลรวม subsequence สูงสุด ระยะห่างอย่างน้อย k ใน C++

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

ตัวอย่าง: arr=[2,3,7,9,2,8,3], k=2 → 15 (เลือก 7 และ 8 ห่าง 3 ตำแหน่ง)

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

dp[i] = ผลรวมสูงสุดจาก arr[i..n-1] ถ้า i+k+1 >= n: dp[i] = max(arr[i], dp[i+1]) มิฉะนั้น: dp[i] = max(arr[i] + dp[i+k+1], dp[i+1])

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

#include <bits/stdc++.h>
using namespace std;

int calcMaxSubSeqSum(int arr[], int N, int k) {
    vector dp(N);
    dp[N-1] = arr[N-1];
    for (int i = N-2; i >= 0; i--) {
        if (i + k + 1 >= N)
            dp[i] = max(arr[i], dp[i+1]);
        else
            dp[i] = max(arr[i] + dp[i+k+1], dp[i+1]);
    }
    return dp[0];
}

int main() {
    int arr[] = {50,70,40,50,90,70,60,40,70,50};
    int N = 10, k = 2;
    cout << calcMaxSubSeqSum(arr, N, k); // 230
    return 0;
}

อินพุต

arr[] = {50,70,40,50,90,70,60,40,70,50}, k=2

เอาต์พุต

230