Chương trình tìm độ dài dãy con bitonic dài nhất trong C++

Cho một mảng số. Ta cần tìm độ dài của dãy con bitonic dài nhất. Một dãy được gọi là bitonic nếu nó tăng chặt rồi giảm chặt. Dãy chỉ tăng hoặc chỉ giảm cũng được coi là bitonic.

Ví dụ: nums = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], kích thước 16 → kết quả là 7.

Thuật toán

• Tính mảng increasingSubSeq: độ dài dãy con tăng chặt dài nhất kết thúc tại mỗi vị trí.
• Tính mảng decreasingSubSeq: độ dài dãy con giảm chặt dài nhất bắt đầu tại mỗi vị trí (duyệt ngược).
• Với mỗi vị trí i, độ dài dãy bitonic có đỉnh tại i là increasingSubSeq[i] + decreasingSubSeq[i] - 1.
• Trả về giá trị lớn nhất trong các vị trí.

Ví dụ triển khai (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 << longBitonicSub(arr, n);
    return 0;
}

Đầu vào

[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], 16

Đầu ra

7