Dãy con Bitonic dài nhất

Dãy Bitonic là dãy trước tăng dần sau giảm dần. Cho mảng số nguyên dương, tìm độ dài dãy con Bitonic dài nhất.

Ý tưởng: Tính hai mảng:

• incSubSeq[i]: độ dài LIS kết thúc tại i (từ trái sang phải).
• decSubSeq[i]: độ dài LDS (Longest Decreasing Subsequence) bắt đầu tại i (từ phải sang trái).

Độ dài Bitonic tại đỉnh i là incSubSeq[i] + decSubSeq[i] - 1 (trừ 1 vì phần tử i bị đếm hai lần). Kết quả là max của giá trị này.

Đầu vào và Đầu ra

Đầu vào: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
Đầu ra: Độ dài Bitonic dài nhất = 7

Thuật toán

1. Tính incSubSeq: duyệt i từ 1 đến n-1, j từ 0 đến i-1. Nếu arr[i] > arr[j] và incSubSeq[i] < incSubSeq[j] + 1 thì cập nhật.
2. Tính decSubSeq: duyệt i từ n-2 xuống 0, j từ n-1 xuống i+1. Nếu arr[i] > arr[j] và decSubSeq[i] < decSubSeq[j] + 1 thì cập nhật.
3. Tìm max của incSubSeq[i] + decSubSeq[i] - 1.

Ví dụ C++

#include <iostream>
using namespace std;

int longBitonicSub(int arr[], int size) {
    int *increasingSubSeq = new int[size];
    for (int i = 0; i < size; i++) increasingSubSeq[i] = 1;
    for (int i = 1; i < size; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && increasingSubSeq[i] < increasingSubSeq[j] + 1)
                increasingSubSeq[i] = increasingSubSeq[j] + 1;

    int *decreasingSubSeq = new int[size];
    for (int i = 0; i < size; i++) decreasingSubSeq[i] = 1;
    for (int i = size-2; i >= 0; i--)
        for (int j = size-1; j > i; j--)
            if (arr[i] > arr[j] && decreasingSubSeq[i] < decreasingSubSeq[j] + 1)
                decreasingSubSeq[i] = decreasingSubSeq[j] + 1;

    int max = increasingSubSeq[0] + decreasingSubSeq[0] - 1;
    for (int i = 1; i < size; i++)
        if (increasingSubSeq[i] + decreasingSubSeq[i] - 1 > max)
            max = increasingSubSeq[i] + decreasingSubSeq[i] - 1;
    return max;
}

int main() {
    int arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
    int n = 16;
    cout << "Length of longest bitonic subsequence is " << longBitonicSub(arr, n);
}

Kết quả

Length of longest bitonic subsequence is 7