Dãy con tăng tổng lớn nhất từ tiền tố và bắt buộc chứa phần tử sau tiền tố (C++)

Cho mảng arr[], chỉ số x, y. Tìm dãy con tăng có tổng lớn nhất chỉ dùng phần tử từ chỉ số 0..x, và bắt buộc chứa arr[y] (với y > x).

Ví dụ: arr=[1,5,9,131,6,100,11,215], x=4, y=6 → dãy con: {1,5,9,11} (từ 0..4 lấy 1,5,9; thêm arr[6]=11) → tổng 26.

Phương pháp Quy hoạch động (DP)

Cách 1 (DP 2D): DP[i][j] = max sum dãy con tăng kết thúc tại j chỉ dùng phần tử 0..i. Khởi tạo DP[0][j]. Chuyển trạng thái: DP[i][j] = max(DP[i-1][j], DP[i-1][i]+arr[j]) nếu arr[j]>arr[i] và j>i.

Cách 2 (Hiệu quả hơn): Chỉ cần tìm max sum dãy con tăng trong 0..x với phần tử lớn nhất < arr[y]. DP 1 chiều: dp[i] = max sum dãy con tăng kết thúc tại i (i≤x, arr[i]

Ví dụ (C++ - Cách 2)

#include <iostream>
using namespace std;

int calcMaxSum(int arr[], int n, int x, int y){
    int DP[x+1]={0}, 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]);
    }
    return (maxSum==-1)? arr[y] : maxSum+arr[y];
}

int main(){
    int arr[]={1,5,9,131,6,100,11,215};
    int N=sizeof(arr)/sizeof(arr[0]), x=4, y=6;
    cout<<calcMaxSum(arr,N,x,y);
    return 0;
}

Đầu ra

26