Tìm tổng lớn nhất của các bộ ba trong mảng sao cho i < j < k và a[i] < a[j] < a[k] trong C++

Khái niệm

Cho một mảng các số nguyên dương kích thước n, nhiệm vụ là xác định tổng lớn nhất của bộ ba (a_i + a_j + a_k) sao cho 0 <= i < j < k < n và a_i< a_j< a_k.

Đầu vào

a[] = 3 6 4 2 5 10

Đầu ra

19

Giải thích

Tất cả các bộ ba có thể: 
3 4 5 => sum = 12
3 6 10 => sum = 19
3 4 10 => sum = 17
4 5 10 => sum = 19
2 5 10 => sum = 17
Tổng lớn nhất = 19

Phương pháp

Một phương pháp đơn giản là duyệt qua mọi bộ ba bằng ba vòng lặp 'for' lồng nhau và cập nhật tổng của tất cả các bộ ba. Độ phức tạp thời gian của phương pháp này là O(n^3), không phù hợp với giá trị n lớn.

Chúng ta có thể áp dụng phương pháp tốt hơn để tối ưu hóa hơn. Thay vì duyệt qua mọi bộ ba bằng ba vòng lặp lồng nhau, ta chỉ dùng hai vòng lặp lồng nhau.

Khi duyệt qua từng số (xem như phần tử giữa a_j), tìm số lớn nhất (a_i) nhỏ hơn a_j đứng trước nó và số lớn nhất (a_k) lớn hơn a_j đứng sau nó. Cuối cùng, cập nhật đáp án lớn nhất với tổng tính được a_i + a_j + a_k.

Ví dụ

// Chương trình C++ tìm tổng lớn nhất của bộ ba
#include <bits/stdc++.h>
using namespace std;

// Hàm tính tổng lớn nhất của bộ ba
int maxTripletSum(int arr1[], int n1){
    // Khởi tạo đáp án
    int ans1 = 0;
    for (int i = 1; i < n1 - 1; ++i) {
        int max1 = 0, max2 = 0;
        // Tìm giá trị lớn nhất (nhỏ hơn arr1[i]) từ 0 đến i-1
        for (int j = 0; j < i; ++j)
            if (arr1[j] < arr1[i])
                max1 = max(max1, arr1[j]);
        // Tìm giá trị lớn nhất (lớn hơn arr1[i]) từ i+1 đến n1-1
        for (int j = i + 1; j < n1; ++j)
            if (arr1[j] > arr1[i])
                max2 = max(max2, arr1[j]);
        // Cập nhật đáp án lớn nhất
        if(max1 && max2)
            ans1 = max(ans1, max1 + arr1[i] + max2);
    }
    return ans1;
}

// Chương trình chính
int main(){
    int Arr[] = { 3, 6, 4, 2, 5, 10 };
    int N = sizeof(Arr) / sizeof(Arr[0]);
    cout << maxTripletSum(Arr, N);
    return 0;
}

Đầu ra

19