Dãy con tăng dần có tổng lớn nhất

Cho dãy số nguyên, tìm dãy con tăng dần (không cần liên tiếp) có tổng phần tử lớn nhất.

Khác với LIS (tìm độ dài), bài này tối ưu tổng. Mảng subSeqLen[i] lưu dãy con tăng dần kết thúc tại i có tổng lớn nhất.

Đầu vào và Đầu ra

Đầu vào: {3, 2, 6, 4, 5, 1}
Đầu ra: Maximum Sum Subsequence: 3 4 5 (tổng = 12)

Thuật toán

1. subSeqLen[0] = {arr[0]}.
2. Với i từ 1 đến n-1:
   • Với j từ 0 đến i-1: nếu arr[i] > arr[j] và sum(subSeqLen[i]) < sum(subSeqLen[j]) thì subSeqLen[i] = subSeqLen[j].
   • Thêm arr[i] vào subSeqLen[i].
3. Tìm dãy có tổng lớn nhất trong subSeqLen.

Ví dụ C++

#include <iostream>
#include <vector>
using namespace std;

int findAllSum(vector<int> arr) {
    int sum=0; for(int x:arr) sum+=x; return sum;
}

void maxSumSubSeq(int arr[], int n) {
    vector<vector<int>> subSeqLen(n);
    subSeqLen[0].push_back(arr[0]);
    for(int i=1;i<n;i++) {
        for(int j=0;j<i;j++)
            if(arr[i]>arr[j] && findAllSum(subSeqLen[i]) < findAllSum(subSeqLen[j]))
                subSeqLen[i] = subSeqLen[j];
        subSeqLen[i].push_back(arr[i]);
    }
    vector<int> res = subSeqLen[0];
    for(int i=0;i<n;i++) if(findAllSum(subSeqLen[i]) > findAllSum(res)) res = subSeqLen[i];
    for(int x:res) cout << x << " ";
}

int main() {
    int arr[] = {3,2,6,4,5,1};
    cout << "The Maximum Sum Subsequence is: ";
    maxSumSubSeq(arr,6);
}

Kết quả

The Maximum Sum Subsequence is: 3 4 5