C++の配列の最大トリプレット合計

この問題では、配列が与えられます。私たちのタスクは、配列内の最大のトリプレット合計を見つけるプログラムを作成することです。つまり、合計が最大である3つの要素のセットを見つけます。

問題を理解するために例を見てみましょう

入力 −配列={4、6、1、2}

出力 − 12

説明 −

all triplets are :
(4, 6, 1) = 4+6+1 = 11
(4, 6, 2) = 4+6+1 = 12
(4, 1, 2) = 4+6+1 = 7
(6, 1, 2) = 4+6+1 = 9
The maximum triplet sum is 12

この問題を解決するための簡単なアプローチの1つは、例で示したものです。これは、すべてのトリプレットペアの合計値を取得し、それらの最大値を見つけることです。しかし、トリプレットの数がすべて長くなると、このアプローチは効果的ではありません。

この方法では、考えられるすべての合計トリプレットを見つける3つのループを実行し、このトリプレットの合計がmaxsumより大きい場合、このトリプレットの合計をmaxsumとして初期化します。

例

ソリューションを説明するプログラム

#include <iostream>
using namespace std;
int maxSum(int arr[], int n){
   int maxSum = 0;
   int i, j, k;
   for (i = 0; i < n; i++)
      for (j = i + 1; j < n; j++)
         for (k = j + 1; k < n; k++)
            if (maxSum < arr[i] + arr[j] + arr[k]) maxSum = arr[i] + arr[j] + arr[k];
   return maxSum;
}
int main(){
   int arr[] = { 3, 5, 7 ,1, 9, 0 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum triplet sum of the array is "<<maxSum(arr, n);
   return 0;
}

出力

The maximum triplet sum of the array is 21

効果的なアプローチは、配列を並べ替えてから、配列の最後の3つの要素の合計を見つけることです。これは、トリプレットの最大合計になります。

例

ソリューションを説明するプログラム

#include <bits/stdc++.h>
using namespace std;
int maxSum(int arr[], int n) {
   sort(arr, arr + n);
   return arr[n - 1] + arr[n - 2] + arr[n - 3];
}
int main() {
   int arr[] = { 3, 5, 9, 1, 2, 8, 7 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum triplet sum of the array is "<<maxSum(arr, n);
   return 0;
}

出力

The maximum triplet sum of the array is 24