數組中的最大三元組和 · GeeksForGeeks 中文系列教程

# 數組中的最大三元組和 > 原文： [https://www.geeksforgeeks.org/maximum-triplet-sum-array/](https://www.geeksforgeeks.org/maximum-triplet-sum-array/) 給定一個數組，任務是在數組中找到最大三元組和。 **示例**： ``` Input : arr[] = {1, 2, 3, 0, -1, 8, 10} Output : 21 10 + 8 + 3 = 21 Input : arr[] = {9, 8, 20, 3, 4, -1, 0} Output : 37 20 + 9 + 8 = 37 ``` **樸素的方法**：在此方法中，我們簡單地運行三個循環，然后一個接一個地添加三個元素，如果三個元素的和更大，則與先前的和進行比較，然后存儲在先前的和中。 ## C++ ```cpp // C++ code to find maximum triplet sum #include <bits/stdc++.h> using namespace std; int maxTripletSum(int arr[], int n) { ????// Initialize sum with INT_MIN ????int sum = INT_MIN; ????for (int i = 0; i < n; i++) ????????for (int j = i + 1; j < n; j++) ????????????for (int k = j + 1; k < n; k++)? ????????????????if (sum < arr[i] + arr[j] + arr[k])? ????????????????????sum = arr[i] + arr[j] + arr[k];???????????????? ????return sum;????????? } // Driven code int main() { ????int arr[] = { 1, 0, 8, 6, 4, 2 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????cout << maxTripletSum(arr, n); ????return 0; } ``` ## Java ```java // Java code to find maximum triplet sum import java.io.*; class GFG { ????static int maxTripletSum(int arr[], int n) ????{ ????????// Initialize sum with INT_MIN ????????int sum = -1000000; ????????for (int i = 0; i < n; i++) ????????????for (int j = i + 1; j < n; j++) ????????????????for (int k = j + 1; k < n; k++)? ????????????????????if (sum < arr[i] + arr[j] + arr[k])? ????????????????????????sum = arr[i] + arr[j] + arr[k];????????????? ????????return sum;????????? ????} ????// Driven code ????public static void main(String args[]) ????{ ????????int arr[] = { 1, 0, 8, 6, 4, 2 }; ????????int n = arr.length; ????????System.out.println(maxTripletSum(arr, n)); ????} } // This code is contributed by Nikita Tiwari. ``` ## Python3 ```py # Python 3 code to find # maximum triplet sum def maxTripletSum(arr, n) : ????# Initialize sum with ????# INT_MIN ????sm = -1000000 ????for i in range(0, n) : ????????for j in range(i + 1, n) : ????????????for k in range(j + 1, n) : ????????????????if (sm < (arr[i] + arr[j] + arr[k])) : ????????????????????sm = arr[i] + arr[j] + arr[k]????????????? ????return sm # Driven code arr = [ 1, 0, 8, 6, 4, 2 ] n = len(arr) print(maxTripletSum(arr, n)) # This code is contributed by Nikita Tiwari. ``` ## C# ```cs // C# code to find maximum triplet sum using System; class GFG { ????static int maxTripletSum(int[] arr, int n) ????{ ????????// Initialize sum with INT_MIN ????????int sum = -1000000; ????????for (int i = 0; i < n; i++) ????????????for (int j = i + 1; j < n; j++) ????????????????for (int k = j + 1; k < n; k++) ????????????????????if (sum < arr[i] + arr[j] + arr[k]) ????????????????????????sum = arr[i] + arr[j] + arr[k]; ????????return sum; ????} ????// Driven code ????public static void Main() ????{ ????????int[] arr = { 1, 0, 8, 6, 4, 2 }; ????????int n = arr.Length; ????????Console.WriteLine(maxTripletSum(arr, n)); ????} } // This code is contributed by vt_m. ``` ## PHP ```php <?php // PHP code to find maximum triplet sum function maxTripletSum( $arr, $n) { ????// Initialize sum with INT_MIN ????$sum = PHP_INT_MIN; ????for($i = 0; $i < $n; $i++) ????????for($j = $i + 1; $j < $n; $j++) ????????????for($k = $j + 1; $k < $n; $k++)? ????????????????if ($sum < $arr[$i] +? ???????????????????????????$arr[$j] + ???????????????????????????$arr[$k]) ????????????????????$sum = $arr[$i] +? ???????????????????????????$arr[$j] + ???????????????????????????$arr[$k];????????? ????return $sum;????????? } ????// Driver Code ????$arr = array(1, 0, 8, 6, 4, 2); ????$n = count($arr); ????echo maxTripletSum($arr, $n); // This code is contributed by anuj_67\. ?> ``` **輸出**： ``` 18 ``` 時間復雜度：O（n ^ 3）空間復雜度：`O(1)` **另一種方法**：在這種情況下，我們首先需要對整個數組進行排序，然后，當我們添加數組的最后三個元素時，我們將找到三叉樹的最大和。 ## C++ ``` // C++ code to find maximum triplet sum #include <bits/stdc++.h> using namespace std; // This function assumes that there are at least? // three elements in arr[]. int maxTripletSum(int arr[], int n) { ????// sort the given array ????sort(arr, arr + n); ????// After sorting the array.? ????// Add last three element of the given array ????return arr[n - 1] + arr[n - 2] + arr[n - 3]; } // Driven code int main() { ????int arr[] = { 1, 0, 8, 6, 4, 2 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????cout << maxTripletSum(arr, n); ????return 0; } ``` ## Java ```java // Java code to find maximum triplet sum import java.io.*; import java.util.*; class GFG { ????// This function assumes that there are ????// at least three elements in arr[]. ????static int maxTripletSum(int arr[], int n) ????{ ????????// sort the given array ????????Arrays.sort(arr); ????????// After sorting the array.? ????????// Add last three element? ????????// of the given array ????????return arr[n - 1] + arr[n - 2] + arr[n - 3]; ????}? ????// Driven code ????public static void main(String args[]) ????{ ????????int arr[] = { 1, 0, 8, 6, 4, 2 }; ????????int n = arr.length; ????????System.out.println(maxTripletSum(arr, n)); ????} } // This code is contributed by Nikita Tiwari. ``` ## Python3 ```py # Python 3 code to find? # maximum triplet sum # This function assumes? # that there are at least? # three elements in arr[]. def maxTripletSum(arr, n) : ????# sort the given array ????arr.sort() ????# After sorting the array.? ????# Add last three element? ????# of the given array ????return (arr[n - 1] + arr[n - 2] + arr[n - 3]) # Driven code arr = [ 1, 0, 8, 6, 4, 2 ] n = len(arr) print(maxTripletSum(arr, n)) # This code is contributed by Nikita Tiwari. ``` ## C# ``` // C# code to find maximum triplet sum using System; class GFG { ????// This function assumes that there are ????// at least three elements in arr[]. ????static int maxTripletSum(int[] arr, int n) ????{ ????????// sort the given array ????????Array.Sort(arr); ????????// After sorting the array. ????????// Add last three element ????????// of the given array ????????return arr[n - 1] + arr[n - 2] + arr[n - 3]; ????} ????// Driven code ????public static void Main() ????{ ????????int[] arr = { 1, 0, 8, 6, 4, 2 }; ????????int n = arr.Length; ????????Console.WriteLine(maxTripletSum(arr, n)); ????} } // This code is contributed by vt_m. ``` ## PHP ```php <?php // PHP code to find? // maximum triplet sum // This function assumes that // there are at least? // three elements in arr[]. function maxTripletSum( $arr, $n) { ????// sort the given array ????sort($arr); ????// After sorting the array.? ????// Add last three element? ????// of the given array ????return $arr[$n - 1] + $arr[$n - 2] + ??????????????????????????$arr[$n - 3]; } // Driver code $arr = array( 1, 0, 8, 6, 4, 2 ); $n = count($arr); echo maxTripletSum($arr, $n); // This code is contributed by anuj_67\. ?> ``` **輸出**： ``` 18 ``` 時間復雜度：O（nlogn）空間復雜度：`O(1)` **有效方法**：掃描數組并計算數組中存在的 Maximum，第二最大和第三最大元素，并返回其總和，即為 max sum。 ## C++ ``` // C++ code to find maximum triplet sum #include <bits/stdc++.h> using namespace std; // This function assumes that there are at least? // three elements in arr[]. int maxTripletSum(int arr[], int n) { ????// Initialize Maximum, second maximum and third ????// maximum element ????int maxA = INT_MIN, maxB = INT_MIN, maxC = INT_MIN; ????for (int i = 0; i < n; i++) { ????????// Update Maximum, second maximum and third ????????// maximum element ????????if (arr[i] > maxA) { ????????????maxC = maxB; ????????????maxB = maxA; ????????????maxA = arr[i]; ????????} ????????// Update second maximum and third maximum ????????// element ????????else if (arr[i] > maxB) { ????????????maxC = maxB; ????????????maxB = arr[i]; ????????} ????????// Update third maximum element ????????else if (arr[i] > maxC) ????????????maxC = arr[i]; ????} ????return (maxA + maxB + maxC); } // Driven code int main() { ????int arr[] = { 1, 0, 8, 6, 4, 2 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????cout << maxTripletSum(arr, n); ????return 0; } ``` ## Java ```java // Java code to find maximum triplet sum import java.io.*; import java.util.*; class GFG { ????// This function assumes that there? ????// are at least? three elements in arr[]. ????static int maxTripletSum(int arr[], int n) ????{ ????????// Initialize Maximum, second maximum and third ????????// maximum element ????????int maxA = -100000000, maxB = -100000000; ????????int maxC = -100000000; ????????for (int i = 0; i < n; i++) { ????????????// Update Maximum, second maximum? ????????????// and third maximum element ????????????if (arr[i] > maxA)? ????????????{ ????????????????maxC = maxB; ????????????????maxB = maxA; ????????????????maxA = arr[i]; ????????????} ????????????// Update second maximum and third maximum ????????????// element ????????????else if (arr[i] > maxB)? ????????????{ ????????????????maxC = maxB; ????????????????maxB = arr[i]; ????????????} ????????????// Update third maximum element ????????????else if (arr[i] > maxC) ????????????????maxC = arr[i]; ????????} ????????return (maxA + maxB + maxC); ????} ????// Driven code ????public static void main(String args[]) ????{ ????????int arr[] = { 1, 0, 8, 6, 4, 2 }; ????????int n = arr.length; ????????System.out.println(maxTripletSum(arr, n)); ????} } // This code is contributed by Nikita Tiwari. ``` ## Python3 ```py # Python 3 code to find? # maximum triplet sum # This function assumes? # that there are at least? # three elements in arr[]. def maxTripletSum(arr, n) : ????# Initialize Maximum, second? ????# maximum and third maximum? ????# element ????maxA = -100000000 ????maxB = -100000000 ????maxC = -100000000 ????for i in range(0, n) : ????????# Update Maximum, second maximum ????????# and third? maximum element ????????if (arr[i] > maxA) : ????????????maxC = maxB ????????????maxB = maxA ????????????maxA = arr[i] ????????# Update second maximum and? ????????# third maximum element ????????elif (arr[i] > maxB) : ????????????maxC = maxB ????????????maxB = arr[i] ????????# Update third maximum element ????????elif (arr[i] > maxC) : ????????????maxC = arr[i] ????return (maxA + maxB + maxC) # Driven code arr = [ 1, 0, 8, 6, 4, 2 ] n = len(arr) print(maxTripletSum(arr, n)) # This code is contributed by Nikita Tiwari. ``` ## C# ``` // C# code to find maximum triplet sum using System; class GFG { ????// This function assumes that there ????// are at least three elements in arr[]. ????static int maxTripletSum(int[] arr, int n) ????{ ????????// Initialize Maximum, second maximum ????????// and third maximum element ????????int maxA = -100000000, maxB = -100000000; ????????int maxC = -100000000; ????????for (int i = 0; i < n; i++) { ????????????// Update Maximum, second maximum ????????????// and third maximum element ????????????if (arr[i] > maxA) { ????????????????maxC = maxB; ????????????????maxB = maxA; ????????????????maxA = arr[i]; ????????????} ????????????// Update second maximum and third ????????????// maximum element ????????????else if (arr[i] > maxB) { ????????????????maxC = maxB; ????????????????maxB = arr[i]; ????????????} ????????????// Update third maximum element ????????????else if (arr[i] > maxC) ????????????????maxC = arr[i]; ????????} ????????return (maxA + maxB + maxC); ????} ????// Driven code ????public static void Main() ????{ ????????int[] arr = { 1, 0, 8, 6, 4, 2 }; ????????int n = arr.Length; ????????Console.WriteLine(maxTripletSum(arr, n)); ????} } // This code is contributed by vt_m. ``` ## PHP ```php <?php // PHP code to find? // maximum triplet sum // This function assumes that? // there are at least three // elements in arr[]. function maxTripletSum($arr, $n) { ????// Initialize Maximum,? ????// second maximum and? ????// third maximum element ????$maxA = PHP_INT_MIN;? ????$maxB = PHP_INT_MIN;? ????$maxC = PHP_INT_MIN; ????for ( $i = 0; $i < $n; $i++)? ????{ ????????// Update Maximum, ????????// second maximum and? ????????// third maximum element ????????if ($arr[$i] > $maxA)? ????????{ ????????????$maxC = $maxB; ????????????$maxB = $maxA; ????????????$maxA = $arr[$i]; ????????} ????????// Update second maximum and? ????????// third maximum element ????????else if ($arr[$i] > $maxB)? ????????{ ????????????$maxC = $maxB; ????????????$maxB = $arr[$i]; ????????} ????????// Update third maximum element ????????else if ($arr[$i] > $maxC) ????????????$maxC = $arr[$i]; ????} ????return ($maxA + $maxB + $maxC); } // Driven code $arr = array( 1, 0, 8, 6, 4, 2 ); $n = count($arr); echo maxTripletSum($arr, $n); // This code is contributed by anuj_67\. ?> ``` **輸出**： ``` 18 ``` **時間復雜度**：`O(n)` **空間復雜度**：`O(1)` * * * * * *