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

แนวคิด

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

อินพุต

a[] =3 6 4 2 5 10

ผลลัพธ์

คำอธิบาย

แฝดสามที่เป็นไปได้ทั้งหมดคือ:-3 4 5 => sum =123 6 10 => sum =193 4 10 => sum =174 5 10 => sum =192 5 10 => sum =17ผลรวมสูงสุด =19 วิธีการ
 
 ตอนนี้ วิธีการง่ายๆ คือการไปเยี่ยมลูกแฝดสามทุกตัวที่มี 'for loops' ซ้อนกันสามตัว และกำหนดการอัปเดตผลรวมของแฝดแฝดทั้งหมดทีละตัว ความซับซ้อนของเวลาของวิธีนี้คือ O(n^3) ซึ่งไม่เพียงพอสำหรับค่า 'n' ที่สูงขึ้น
 
 อีกครั้ง เราสามารถใช้แนวทางที่ดีกว่า เพื่อการเพิ่มประสิทธิภาพเพิ่มเติมในแนวทางข้างต้น ในวิธีนี้ แทนที่จะตรวจดู Triplet ทุกตัวที่มีลูปซ้อนกันสามอัน เราสามารถเข้าไปที่ลูปสองอันที่ซ้อนกันได้
 
 ในช่วงเวลาของการเยี่ยมชมแต่ละหมายเลข(ปล่อยให้เป็นองค์ประกอบกลาง(a_j )) กำหนดจำนวนสูงสุด (a_i ) น้อยกว่า a_j นำหน้าและจำนวนสูงสุด(ak ) ที่มากกว่า a_j เกินกว่านั้น สุดท้ายนี้ ให้อัปเดตคำตอบสูงสุดด้วยผลรวมที่คำนวณได้ของ a_i + a_j + a_k 
 ตัวอย่าง
 // โปรแกรม C++ เพื่อค้นหาผลรวมของ triplet สูงสุด#include โดยใช้เนมสเปซ std;// แสดงฟังก์ชันเพื่อคำนวณค่าสูงสุดของ triplet sumint maxTripletSum(int arr1[], int n1){ // ใช้เพื่อเริ่มต้น คำตอบ int ans1 =0; สำหรับ (int i =1; i  arr1[i ]) max2 =สูงสุด (max2, arr1[j]); // เก็บคำตอบสูงสุด if(max1 &&max2) ans1=max(ans1,max1+arr1[i]+max2); } return ans1;}// รหัสไดรเวอร์ main(){ int Arr[] ={ 3, 6, 4, 2, 5, 10 }; int ยังไม่มีข้อความ =sizeof(Arr) / sizeof(Arr[0]); ศาล < ผลลัพธ์
 19