โจทย์: หา triplet (a[i], a[j], a[k]) ที่ i

ตัวอย่าง: A=[3,6,4,2,5,10] → triplets ที่ valid: (3,4,5)=12, (3,6,10)=19, (3,4,10)=17, (4,5,10)=19, (2,5,10)=17 → max = 19

อัลกอริทึม O(n²)

fixed j เป็นกลาง หา max a[i] < a[j] ด้านซ้าย และ max a[k] > a[j] ด้านขวา

1. วน j จาก 1 ถึง n-2
2. หา first_max = max{a[i] | i
3. หา second_max = max{a[k] | k>j, a[k]>a[j]}
4. ถ้าทั้งคู่มีอยู่ → อัปเดตคำตอบ = max(คำตอบ, first_max + a[j] + second_max)

ตัวอย่างโค้ด

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(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))  # 19

ผลลัพธ์

19

หมายเหตุ: สามารถ optimize เป็น O(n log n) ได้ด้วย Segment Tree หรือ BIT สำหรับ n ใหญ่