컨셉

크기가 n인 양의 정수의 주어진 배열과 관련하여 삼중항의 최대합( a_i + a_j + a_k ) 0 <=i i j k .

입력

a[] =3 6 4 2 5 10

출력

19

설명

가능한 모든 삼중항은 다음과 같습니다.-3 4 5 => 합계 =123 6 10 => 합계 =193 4 10 => 합계 =174 5 10 => 합계 =192 5 10 => 합계 =17최대 합계 =19 
방법
 

 이제 간단한 접근 방식 세 개의 중첩된 'for 루프'가 있는 모든 삼중항을 방문하고 모든 삼중항의 합을 하나씩 업데이트하도록 결정하는 것입니다. 여기서 이 방법의 시간복잡도는 O(n^3)으로 'n'의 높은 값에 충분하지 않습니다.
 

 다시 한 번 더 나은 접근 방식을 적용할 수 있습니다. 위의 접근 방식에서 추가 최적화를 위해. 이 방법에서는 세 개의 중첩 루프가 있는 모든 트리플렛을 방문하는 대신 두 개의 중첩 루프를 통해 방문할 수 있습니다.
 

 각 번호를 통해 방문할 때(중간 요소(aj )), 최대 수를 결정합니다(ai ) aj보다 작음 그 앞에 있고 aj보다 큰 최대 수(ak) 그 너머. 마지막으로 이제 i의 계산된 합계로 최대 답변을 업데이트합니다. + aj + ak 
 
예시
 
// 최대 삼중항을 구하는 C++ 프로그램 sum#include using namespace std;// 최대 삼중항 계산 함수 표시 sumt maxTripletSum(int arr1[], int n1){ // 초기화에 사용 답변 int ans1 =0; for (int i =1; i  arr1[i ]) 최대2 =최대(최대2, arr1[j]); // 최대 답변 저장 if(max1 &&max2) ans1=max(ans1,max1+arr1[i]+max2); } return ans1;}// 드라이버 codeint main(){ int Arr[] ={ 3, 6, 4, 2, 5, 10 }; int N =sizeof(Arr) / sizeof(Arr[0]); cout < 
출력
 
19