หาผลรวมสูงสุดของ Triplet ในอาร์เรย์ที่ i < j < k และ a[i] < a[j] < a[k] ใน C++

แนวคิด

เมื่อได้รับอาร์เรย์ของจำนวนเต็มบวกขนาด n งานของเราคือการหาผลรวมสูงสุดของ triplet (a_i + a_j + a_k) ที่ทำให้ 0 <= i < j < k < n และ a_i< a_j< a_k

อินพุต

a[] = 3 6 4 2 5 10

เอาต์พุต

19

คำอธิบาย

Triplet ที่เป็นไปได้ทั้งหมด:- 3 4 5 => ผลรวม = 12 3 6 10 => ผลรวม = 19 3 4 10 => ผลรวม = 17 4 5 10 => ผลรวม = 19 2 5 10 => ผลรวม = 17 ผลรวมสูงสุด = 19

วิธีการ

วิธีง่ายๆ คือการตรวจสอบทุก triplet ด้วย 3 วนลูปซ้อนกันและอัปเดตผลรวมของแต่ละ triplet ทีละอัน เวลา Complexity ของวิธีนี้คือ O(n^3) ซึ่งไม่เหมาะสำหรับค่า n ที่สูง

วิธีที่ดีกว่า สำหรับการเพิ่มประสิทธิภาพเพิ่มเติม ในวิธีนี้แทนที่จะตรวจสอบทุก triplet ด้วย 3 วนลูปซ้อนกัน เราสามารถใช้ 2 วนลูปซ้อนกันแทนได้

ขณะตรวจสอบแต่ละตัวเลข (ให้เป็น middle element a_j) ให้หาตัวเลขสูงสุด (a_i) ที่น้อยกว่า a_j อยู่ก่อนหน้า และตัวเลขสูงสุด (a_k) ที่มากกว่า a_j อยู่ด้านหลัง สุดท้ายให้อัปเดตคำตอบสูงสุดด้วยผลรวมที่คำนวณได้ของ a_i + a_j + a_k

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

// โปรแกรม C++ เพื่อหาผลรวม triplet สูงสุด #include <bits/stdc++.h> using namespace std; // ฟังก์ชันแสดงการคำนวณผลรวม triplet สูงสุด int maxTripletSum(int arr1[], int n1){    // ใช้ในการเริ่มต้นคำตอบ    int ans1 = 0;    for (int i = 1; i < n1 - 1; ++i) {       int max1 = 0, max2 = 0;       // หาค่าสูงสุด (น้อยกว่า arr1[i])       // จาก i+1 ถึง n1-1       for (int j = 0; j < i; ++j)          if (arr1[j] < arr1[i])             max1 = max(max1, arr1[j]);       // หาค่าสูงสุด (มากกว่า arr1[i])       // จาก i+1 ถึง n1-1       for (int j = i + 1; j < n1; ++j)          if (arr1[j] > arr1[i])             max2 = max(max2, arr1[j]);       // เก็บคำตอบสูงสุด       if(max1 && max2)          ans1=max(ans1,max1+arr1[i]+max2);    }    return ans1; } // โค้ดหลัก int main(){    int Arr[] = { 3, 6, 4, 2, 5, 10 };    int N = sizeof(Arr) / sizeof(Arr[0]);    cout << maxTripletSum(Arr, N);    return 0; }

เอาต์พุต

19