Maximum Sum Increasing Subsequence

Maximum Sum Increasing Subsequence (MSIS) คือ subsequence ที่:

1. เรียงลำดับเพิ่มขึ้น (Increasing)
2. มีผลรวมของสมาชิกมากที่สุด (Maximum Sum)

ตัวอย่าง Input และ Output

Input: {3, 2, 6, 4, 5, 1}
Output: Maximum Sum Subsequence is: 3 4 5
(Sum = 12, ซึ่งมากกว่า {2, 6} = 8 หรือ {3, 6} = 9)

อัลกอริทึม Dynamic Programming

ฟังก์ชัน maxSumSubSeq(array, n)

แนวคิด:

ใช้ Vector of Vectors: subSeqLen[i] = MSIS ที่ลงท้ายด้วย arr[i] (เก็บ subsequence จริง ไแค่ความยาว)

ขั้นตอน:

1. สร้าง vector> subSeqLen(n)
2. subSeqLen[0] = {arr[0]}
3. for i = 1 ถึง n-1:
   • for j = 0 ถึง i-1:
     • ถ้า arr[i] > arr[j] และ sum(subSeqLen[i]) < sum(subSeqLen[j])
     • → subSeqLen[i] = subSeqLen[j] (คัดลอก subsequence ที่ดีกว่า)
   • subSeqLen[i].push_back(arr[i]) (ต่อท้าย arr[i])
4. หา res = subsequence ที่มี sum มากที่สุดจาก subSeqLen
5. พิมพ์ res

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

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

int findAllSum(vector arr) {
    int sum = 0;
    for(int i = 0; i < arr.size(); i++) sum += arr[i];
    return sum;
}

void maxSumSubSeq(int arr[], int n) {
    vector> 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 res = subSeqLen[0];
    for(int i = 0; i < subSeqLen.size(); i++)
        if (findAllSum(subSeqLen[i]) > findAllSum(res))
            res = subSeqLen[i];

    for(int i = 0; i < res.size(); i++)
        cout << res[i] << " ";
    cout << endl;
}

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

Output

The Maximum Sum Subsequence is: 3 4 5

ความซับซ้อน

• Time: O(n²) (หากคำนวณ sum ทุกครั้ง จะเป็น O(n³) - ควรเก็บ sum ไว้แยก)
• Space: O(n²) - เก็บ subsequence ทั้งหมด

การเพิ่มประสิทธิภาพ (Optimized O(n²) Time, O(n) Space)

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];

    return *max_element(msis, msis+n);
}

เวอร์ชันนี้เก็บแค่ ผลรวม ไม่เก็บ subsequence จริง เร็วกว่าและประหยัดหน่วยความจำ