Tổng lớn nhất của dãy con giảm dần trong C++

Mô tả bài toán

Cho mảng arr[] gồm N số nguyên. Tìm tổng lớn nhất của một dãy con (không nhất thiết liên tiếp) mà các phần tử giảm dần chặt.

Ví dụ: arr = {3, 1, 6, 10, 5, 2, 9} → Dãy con giảm dần có tổng lớn nhất: {10, 5, 2} = 17.

Giải pháp (Quy hoạch động)

• maxSum[i] = tổng lớn nhất của dãy con giảm dần kết thúc tại chỉ số i.
• Khởi tạo maxSum[i] = arr[i].
• Với mỗi i từ 1 đến N-1, với mỗi j < i:
  • Nếu arr[i] < arr[j] và maxSum[i] < maxSum[j] + arr[i] → maxSum[i] = maxSum[j] + arr[i].
• Kết quả = max của mảng maxSum.

Ví dụ minh họa

#include <iostream>
using namespace std;

int findMaxSumDecSubSeq(int arr[], int N) {
    int maximumSum = 0;
    int maxSum[N];
    for (int i = 0; i < N; i++) maxSum[i] = arr[i];
    for (int i = 1; i < N; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] < arr[j] && maxSum[i] < maxSum[j] + arr[i])
                maxSum[i] = maxSum[j] + arr[i];
    for (int i = 0; i < N; i++)
        if (maximumSum < maxSum[i]) maximumSum = maxSum[i];
    return maximumSum;
}

int main() {
    int arr[] = {5, 4, 100, 3, 2, 101, 1};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum sum of decreasing subsequence is " << findMaxSumDecSubSeq(arr, N);
    return 0;
}

Đầu ra

The maximum sum of decreasing subsequence is 106