โปรแกรมหาผลรวมส่วนย่อยสูงสุดไม่มีสมาชิกติดกันใน C++ (วิธี DP)

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

ตัวอย่าง: arr=[5,2,1,9,6] → 14 (เลือก 5,1,6 หรือ 5,9)

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

dp[i] = ผลรวมสูงสุดจาก arr[i..n-1] dp[i] = max(arr[i] + dp[i+2], dp[i+1]) Base: dp[n-1]=arr[n-1], dp[n-2]=max(arr[n-1],arr[n-2])

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

#include <iostream>
using namespace std;

int calcMaxSum(int arr[], int n) {
    vector dp(n);
    dp[n-1] = arr[n-1];
    dp[n-2] = max(arr[n-1], arr[n-2]);
    for (int i = n-3; i >= 0; i--)
        dp[i] = max(arr[i] + dp[i+2], dp[i+1]);
    return dp[0];
}

int main() {
    int arr[] = {5,2,1,9,6};
    int n = 5;
    cout << calcMaxSum(arr, n); // 14
    return 0;
}

อินพุต

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

เอาต์พุต

14