Tổng lớn nhất dãy con không có hai phần tử liền kề (phương pháp thay thế) trong C++

Mô tả bài toán

Cho mảng arr[] toàn số dương. Tìm tổng lớn nhất của dãy con (không nhất thiết liên tiếp) sao cho không lấy hai phần tử liền kề trong mảng gốc.

Ví dụ: arr = {5,2,1,9,6} → 14 (chọn 5,1,6 hoặc 5,9).

Giải thuật (Quy hoạch động)

1. maxSumDP[i] = tổng lớn nhất từ i đến n-1.
2. maxSumDP[n-1] = arr[n-1]; maxSumDP[n-2] = max(arr[n-1], arr[n-2]).
3. Với i từ n-3 xuống 0: maxSumDP[i] = max(arr[i] + maxSumDP[i+2], maxSumDP[i+1]).
4. Kết quả maxSumDP[0].

Ví dụ minh họa (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 << "Maximum sum: " << calcMaxSum(arr, n);
    return 0;
}

Đầu ra

Maximum sum: 14