Maximum Sum Increasing Subsequence ด้วย Binary Indexed Tree ใน C++

โจทย์

กำหนดอาร์เรย์ arr[] ขนาด N หา Maximum Sum Increasing Subsequence (MSIS) ใช้ Binary Indexed Tree (Fenwick Tree)

ตัวอย่าง: arr = {4, 1, 9, 2, 3, 7} → MSIS = {1, 2, 3, 7} Sum = 13

วิธีการแก้ปัญหา

1. Coordinate Compression: Map ค่าในอาร์เรย์เป็น index 1..M (เรียง unique values)
2. BIT เก็บ max sum สำหรับแต่ละ prefix
3. สำหรับแต่ละ arr[i]: query BIT หา max sum ของค่าที่ < arr[i] → maxSum, แล้ว update BIT ที่ index ของ arr[i] ด้วย maxSum + arr[i]
4. คำตอบ = query BIT ทั้งหมด

Time: O(N log N)

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

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

int calcMaxSum(int BITree[], int index){
    int maxSum = 0;
    while (index > 0){
        maxSum = max(maxSum, BITree[index]);
        index -= index & (-index);
    }
    return maxSum;
}

void updateBIT(int BITree[], int newIndex, int index, int val){
    while (index <= newIndex){
        BITree[index] = max(val, BITree[index]);
        index += index & (-index);
    }
}

int maxSumIS(int arr[], int n){
    int index = 0, maxSum;
    map<int, int> arrMap;
    for (int i = 0; i < n; i++) arrMap[arr[i]] = 0;
    for (auto it = arrMap.begin(); it != arrMap.end(); it++){
        index++;
        arrMap[it->first] = index;
    }
    int* BITree = new int[index + 1];
    for (int i = 0; i <= index; i++) BITree[i] = 0;
    for (int i = 0; i < n; i++){
        maxSum = calcMaxSum(BITree, arrMap[arr[i]] - 1);
        updateBIT(BITree, index, arrMap[arr[i]], maxSum + arr[i]);
    }
    return calcMaxSum(BITree, index);
}

int main() {
    int arr[] = {4, 6, 1, 9, 2, 3, 5, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The Maximum sum increasing subsequence using Binary Indexed Tree is " << maxSumIS(arr, n);
    return 0;
}

ผลลัพธ์

The Maximum sum increasing subsequence using Binary Indexed Tree is 19