在C++中找出数组中三元组的最大和
概念
对于给定的大小为n的正整数数组，我们的任务是确定三元组（ai+aj+ak）的最大和，以使0<=i<j<k<k<n和ai<aj<ak。
输入值
a[] = 3 6 4 2 5 10
输出结果
19
说明
All possible triplets are:- 3 4 5 => sum = 12 3 6 10 => sum = 19 3 4 10 => sum = 17 4 5 10 => sum = 19 2 5 10 => sum = 17 Maximum sum = 19
方法
现在，一种简单的方法是使用三个嵌套的“for循环”访问每个三元组，并确定一个一个地更新所有三元组的总和。在此，此方法的时间复杂度为O（n^3），对于“n”的较高值来说是不够的。
同样，我们可以应用更好的方法在上述方法中进行进一步的优化。在这种方法中，我们可以通过两个嵌套循环访问，而不是通过三个嵌套循环访问每个三元组。
在通过每个数来访的时间（如让中间元件（Ĵ）），确定最大数量（一个我）小于Ĵ它前面和最大数量(AK)大于aĴ超越它。最后，现在，使用计算出的ai+aj+ak之和更新最大答案
示例
// C++ program to find maximum triplet sum
#include <bits/stdc++.h>
using namespace std;
// Shows function to calculate maximum triplet sum
int maxTripletSum(int arr1[], int n1){
// Used to initialize the answer
int ans1 = 0;
for (int i = 1; i < n1 - 1; ++i) {
int max1 = 0, max2 = 0;
// Determine maximum value(less than arr1[i])
// from i+1 to n1-1
for (int j = 0; j < i; ++j)
if (arr1[j] < arr1[i])
max1 = max(max1, arr1[j]);
// Determine maximum value(greater than arr1[i])
// from i+1 to n1-1
for (int j = i + 1; j < n1; ++j)
if (arr1[j] > arr1[i])
max2 = max(max2, arr1[j]);
// store maximum answer
if(max1 && max2)
ans1=max(ans1,max1+arr1[i]+max2);
}
return ans1;
}
// Driver code
int main(){
int Arr[] = { 3, 6, 4, 2, 5, 10 };
int N = sizeof(Arr) / sizeof(Arr[0]);
cout << maxTripletSum(Arr, N);
return 0;
}输出结果
19