在C++中找出数组中三元组的最大和
概念
对于给定的大小为n的正整数数组，我们的任务是确定三元组（a i + a j + a k）的最大和，以使0 <= i <j <k <k <n和a i <a j <a k。
输入值
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 Ĵ超越它。最后，现在，使用计算出的a i + a j + a k之和更新最大答案
示例
// 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
以上是 在C++中找出数组中三元组的最大和 的全部内容， 来源链接： utcz.com/z/327316.html
