入力

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

メソッド

さて、シンプルなアプローチ 3つのネストされた「forループ」を持つすべてのトリプレットにアクセスし、すべてのトリプレットの合計を1つずつ更新することを決定します。ここで、このメソッドの時間計算量はO（n ^ 3）であり、「n」の値を高くするには不十分です。

繰り返しになりますが、より良いアプローチを適用できます 上記のアプローチでさらに最適化を行うため。この方法では、3つのネストされたループを持つすべてのトリプレットを訪問する代わりに、2つのネストされたループを訪問できます。

各番号を訪問するとき（中間要素（a _j ））、最大数を決定します（a _i ） _j未満 その前にあり、最大数（ak）がa _j より大きい それを超えて。最後に、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