Maximum Sum Increasing Subsequence (DP-14) ใน C++

โจทย์

หา Maximum Sum Increasing Subsequence (MSIS) ของอาร์เรย์ N ตัว คือ subsequence ที่เพิ่มขึ้นและมีผลรวมสูงสุด

ตัวอย่าง: arr = {1, 101, 2, 3, 100, 4, 5} → MSIS = {1, 2, 3, 100} Sum = 106

วิธีการแก้ปัญหา (Dynamic Programming)

DP[i] = max sum increasing subsequence ที่ลงท้ายที่ index i - เริ่มต้น: DP[i] = arr[i] - Transition: DP[i] = max(DP[i], DP[j] + arr[i]) สำหรับทุก j < i ที่ arr[j] < arr[i] - คำตอบ = max(DP[i]) ทุก i

Time: O(N²), Space: O(N)

ตัวอย่างโค้ด C++

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

int maxSumIS(int arr[], int n) {
    int i, j, max = 0;
    int msis[n];
    for (i = 0; i < n; i++)
        msis[i] = arr[i];
    for (i = 1; i < n; i++)
        for (j = 0; j < i; j++)
            if (arr[i] > arr[j] && msis[i] < msis[j] + arr[i])
                msis[i] = msis[j] + arr[i];
    for (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;
}

ผลลัพธ์

Sum of maximum sum increasing subsequence is 106