Tìm tổng lớn nhất của triplet trong mảng với i < j < k và a[i] < a[j] < a[k] trong Python

Cho mảng số dương n phần tử, tìm tổng lớn nhất của triplet (a[i] + a[j] + a[k]) sao cho 0 ≤ i < j < k < n và a[i] < a[j] < a[k].

Ví dụ: A = [3, 6, 4, 2, 5, 10] → Kết quả: 19 (triplet (3,6,10) hoặc (4,5,10)).

Thuật toán O(n²)

1. Duyệt j từ 1 đến n-2 (coi j là phần tử giữa).
2. Tìm first_max = max{a[i] | i < j và a[i] < a[j]}.
3. Tìm second_max = max{a[k] | k > j và a[k] > a[j]}.
4. Nếu cả hai tồn tại, cập nhật res = max(res, first_max + a[j] + second_max).

Ví dụ code

def get_max_triplet_sum(A):
    n = len(A)
    res = 0
    for i in range(1, n - 1):
        first_max = 0
        second_max = 0
        for j in range(0, i):
            if A[j] < A[i]:
                first_max = max(first_max, A[j])
        for j in range(i + 1, n):
            if A[j] > A[i]:
                second_max = max(second_max, A[j])
        if first_max and second_max:
            res = max(res, first_max + A[i] + second_max)
    return res

A = [3, 6, 4, 2, 5, 10]
print(get_max_triplet_sum(A))

Input

[3, 6, 4, 2, 5, 10]

Output

19