在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