Dãy con tăng tổng lớn nhất (Maximum Sum Increasing Subsequence) - DP cơ bản trong C++

Bài toán kinh điển: cho mảng N số nguyên, tìm dãy con tăng (không cần liên tiếp) có tổng lớn nhất.

Ví dụ: arr=[1,101,2,3,100,4,5] → dãy con: 1,2,3,100 → tổng = 106.

Quy hoạch động O(N²)

• msis[i] = max sum dãy con tăng kết thúc tại i (bắt buộc lấy arr[i]).
• Khởi tạo msis[i] = arr[i].
• Với mỗi i, duyệt j < i: nếu arr[i] > arr[j] và msis[i] < msis[j] + arr[i] → cập nhật msis[i].
• Kết quả = max(msis[i]).

Ví dụ (C++)

#include <bits/stdc++.h>
using namespace std;

int maxSumIS(int arr[], int n){
    int msis[n];
    for(int i=0;i<n;i++) msis[i]=arr[i];
    for(int i=1;i<n;i++)
        for(int j=0;j<i;j++)
            if(arr[i]>arr[j] && msis[i]<msis[j]+arr[i])
                msis[i]=msis[j]+arr[i];
    int max=0;
    for(int i=0;i<n;i++) if(max<msis[i]) max=msis[i];
    return max;
}

int main(){
    int arr[]={1,101,2,3,100,4,5};
    int n=sizeof(arr)/sizeof(arr[0]);
    cout<<"Sum of maximum sum increasing subsequence is "<<maxSumIS(arr,n)<<endl;
    return 0;
}

Đầu ra

Sum of maximum sum increasing subsequence is 106