Maximum Sum Increasing Subsequence จาก Prefix และต้องรวม Element ที่กำหนดใน C++

โจทย์

กำหนดอาร์เรย์ arr[] ขนาด N และ index x, y หา Maximum Sum Increasing Subsequence จาก prefix [0..x] ที่ต้องรวม arr[y] ด้วย (y > x)

ตัวอย่าง: arr = {1, 5, 9, 131, 6, 100, 11, 215}, x=4, y=6 → Subsequence: {1, 5, 9, 11} Sum = 26

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

วิธี 1: 2D DP DP[i][j] = max sum increasing subsequence จนถึง index i ที่ลงท้ายด้วย arr[j] → คำตอบ = DP[x][y]

วิธี 2: 1D DP (มีประสิทธิภาพมากกว่า) - DP[i] = max sum increasing subsequence ลงท้ายที่ i (ใน prefix 0..x) - เงื่อนไข: arr[i] < arr[y] (เพื่อให้ต่อ arr[y] ได้) - คำตอบ = max(DP[i]) + arr[y] โดย i ≤ x และ arr[i] < arr[y]

ตัวอย่างโค้ด C++ (วิธี 1: 2D DP)

#include <iostream>
using namespace std;

int DP[100][100];

void preCalcMaxSum(int arr[], int N){
    for (int i = 0; i < N; i++) {
        if (arr[i] > arr[0]) DP[0][i] = arr[i] + arr[0];
        else DP[0][i] = arr[i];
    }
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[j] > arr[i] && j > i) {
                if (DP[i-1][i] + arr[j] > DP[i-1][j]) DP[i][j] = DP[i-1][i] + arr[j];
                else DP[i][j] = DP[i-1][j];
            } else DP[i][j] = DP[i-1][j];
        }
    }
}

int main() {
    int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
    int N = sizeof(arr) / sizeof(arr[0]);
    int x = 4, y = 6;
    preCalcMaxSum(arr, N);
    cout << "The maximum sum increasing subsequence... is " << DP[x][y];
    return 0;
}

ตัวอย่างโค้ด C++ (วิธี 2: 1D DP - Efficient)

int calcMaxSum(int arr[], int n, int x, int y){
    int DP[x] = {0};
    int maxSum = -1;
    for (int i = 0; i <= x; i++) DP[i] = arr[i];
    for (int i = 0; i <= x; i++) {
        if (arr[i] >= arr[y]) continue;
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j])
                DP[i] = max(DP[i], DP[j] + arr[i]);
            maxSum = max(maxSum, DP[i]);
        }
    }
    if (maxSum == -1) return arr[y];
    return maxSum + arr[y];
}

ผลลัพธ์

The maximum sum increasing subsequence... is 26