Tổng lớn nhất của dãy con Bi-tonic trong C++

Mô tả bài toán

Dãy Bi-tonic (đôi cung) là dãy tăng dần rồi giảm dần. Cho mảng arr[], tìm dãy con Bi-tonic có tổng lớn nhất.

Ví dụ: arr = {4, 2, 3, 7, 9, 6, 3, 5, 1} → Dãy con: {2, 3, 7, 9, 6, 5, 1} = 33.

Giải pháp (Quy hoạch động)

• incSeq[i] = tổng lớn nhất của dãy con tăng dần kết thúc tại i.
• decSeq[i] = tổng lớn nhất của dãy con giảm dần bắt đầu tại i.
• Tính incSeq từ trái sang phải, decSeq từ phải sang trái.
• Kết quả = max(incSeq[i] + decSeq[i] - arr[i]) (trừ arr[i] vì bị đếm 2 lần).

Ví dụ minh họa

#include <iostream>
using namespace std;

int calcMaxVal(int a, int b) { return a > b ? a : b; }

int findMaxSumBiTonicSubSeq(int arr[], int N) {
    int maxSum = -1;
    int incSeq[N], decSeq[N];
    for (int i = 0; i < N; i++) incSeq[i] = decSeq[i] = arr[i];
    for (int i = 1; i < N; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && incSeq[i] < incSeq[j] + arr[i])
                incSeq[i] = incSeq[j] + arr[i];
    for (int i = N - 2; i >= 0; i--)
        for (int j = N - 1; j > i; j--)
            if (arr[i] > arr[j] && decSeq[i] < decSeq[j] + arr[i])
                decSeq[i] = decSeq[j] + arr[i];
    for (int i = 0; i < N; i++)
        maxSum = calcMaxVal(maxSum, incSeq[i] + decSeq[i] - arr[i]);
    return maxSum;
}

int main() {
    int arr[] = {4, 2, 3, 7, 9, 6, 3, 5, 1};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "The Maximum Sum of Bi-tonic subsequence is : " << findMaxSumBiTonicSubSeq(arr, N);
    return 0;
}

Đầu ra

The Maximum Sum of Bi-tonic subsequence is : 33