Tổng lớn nhất của mảng con Bitonic trong C++

Mô tả bài toán

Mảng con Bitonic là mảng con liên tiếp mà các phần tử tăng dần chặt rồi giảm dần chặt. Cho mảng arr[], tìm mảng con Bitonic có tổng lớn nhất.

Ví dụ: arr = {4, 2, 3, 7, 9, 6, 3, 5, 1} → Mảng con: [2, 3, 7, 9, 6, 3] = 30.

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

• incSubArr[i] = tổng mảng con tăng dần kết thúc tại i (liên tiếp).
• decSubArr[i] = tổng mảng con giảm dần bắt đầu tại i (liên tiếp).
• Tính incSubArr từ trái sang: nếu arr[i] > arr[i-1] thì incSubArr[i] = incSubArr[i-1] + arr[i], ngược lại arr[i].
• Tính decSubArr từ phải sang: nếu arr[i] > arr[i+1] thì decSubArr[i] = decSubArr[i+1] + arr[i], ngược lại arr[i].
• Kết quả = max(incSubArr[i] + decSubArr[i] - arr[i]).

Ví dụ minh họa

#include <iostream>
using namespace std;

int findMaxSumBiTonicSubArr(int arr[], int N) {
    int incSubArr[N], decSubArr[N];
    int max_sum = -1;
    incSubArr[0] = arr[0];
    for (int i = 1; i < N; i++)
        incSubArr[i] = (arr[i] > arr[i-1]) ? incSubArr[i-1] + arr[i] : arr[i];
    decSubArr[N-1] = arr[N-1];
    for (int i = N-2; i >= 0; i--)
        decSubArr[i] = (arr[i] > arr[i+1]) ? decSubArr[i+1] + arr[i] : arr[i];
    for (int i = 0; i < N; i++)
        if (max_sum < incSubArr[i] + decSubArr[i] - arr[i])
            max_sum = incSubArr[i] + decSubArr[i] - arr[i];
    return max_sum;
}

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 Bitonic Subarray is " << findMaxSumBiTonicSubArr(arr, N);
    return 0;
}

Đầu ra

The Maximum Sum of Bitonic Subarray is 30