Tìm dãy con tăng dần có tổng lớn nhất sử dụng Quy hoạch động (DP) trong C++

Trong bài toán này, chúng ta được cung cấp một mảng arr[] kích thước n. Nhiệm vụ là viết chương trình tìm dãy con tăng dần có tổng lớn nhất sử dụng Quy hoạch động (DP) trong C++.

Mô tả bài toán

Để tìm dãy con tăng dần có tổng lớn nhất, ta sẽ tạo một dãy con mà phần tử tiếp theo lớn hơn phần tử hiện tại.

Ví dụ minh họa

Đầu vào

arr[] = {4, 2, 3, 6, 5, 9}

Đầu ra

20

Giải thích

Dãy con tăng dần có tổng lớn nhất: {2, 3, 6, 9} = 2 + 3 + 6 + 9 = 20

Phương pháp giải

Để giải bài toán bằng cách tiếp cận Quy hoạch động. Ta tạo một mảng để lưu trữ tổng lớn nhất tính đến phần tử hiện tại. Sau đó trả về maxSum từ mảng đó.

Chương trình minh họa

#include <iostream>
using namespace std;

int retMaxVal(int x, int y) {
    if (x > y)
        return x;
    return y;
}

int calcMaxSubSeqSum(int arr[], int n) {
    int maxSum = 0;
    int sumDP[n];
    
    for (int i = 0; i < n; i++)
        sumDP[i] = arr[i];
    
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if ((sumDP[i] < (sumDP[j] + arr[i])) && (arr[i] > arr[j]))
                sumDP[i] = sumDP[j] + arr[i];
    
    for (int i = 0; i < n; i++)
        maxSum = retMaxVal(sumDP[i], maxSum);
    
    return maxSum;
}

int main() {
    int arr[] = {4, 2, 3, 6, 5, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Dãy con tăng dần có tổng lớn nhất sử dụng DP là "
         << calcMaxSubSeqSum(arr, n);
    return 0;
}

Đầu ra

Tổng dãy con tăng dần lớn nhất là 20