Tổng lớn nhất không có hai phần tử liền kề - Phiên bản 2 (DP) trong C++

Cho mảng arr[]. Tìm tổng lớn nhất của dãy con sao cho không có hai phần tử nào liền kề trong mảng gốc.

Ví dụ

Đầu vào: arr[] = {5, 1, 3, 7, 9, 2, 5}

Đầu ra: 22

Giải thích

Lấy từ chỉ số 0 cách nhau một: 5 + 3 + 9 + 5 = 22
Lấy từ chỉ số 1 cách nhau một: 1 + 7 + 2 = 10

Phương pháp Quy hoạch động

Tạo mảng DP[] lưu tổng lớn nhất đến chỉ số hiện tại. DP[i] = max(DP[i+1], arr[i] + DP[i+2]).

Ví dụ

#include <iostream>
using namespace std;

int DP[100];
bool currState[100];

int maxVal(int a, int b) {
    return (a > b) ? a : b;
}

int calcMaxSumWOAdj(int arr[], int i, int n) {
    if (i >= n) return 0;
    if (currState[i]) return DP[i];
    currState[i] = 1;
    DP[i] = maxVal(calcMaxSumWOAdj(arr, i + 1, n), arr[i] + calcMaxSumWOAdj(arr, i + 2, n));
    return DP[i];
}

int main() {
    int arr[] = {5, 1, 3, 7, 9, 2, 5};
    int n = sizeof(arr) / sizeof(int);
    cout << "Tổng lớn nhất không có 2 phần tử liền kề: " << calcMaxSumWOAdj(arr, 0, n);
    return 0;
}

Đầu ra

Tổng lớn nhất không có 2 phần tử liền kề: 22