# 数组中的最大三元组和

> 原文： [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

```

## [推荐：请先解决 ***<u>惯例</u>*** ，然后再继续解决。](https://practice.geeksforgeeks.org/problems/maximum-triplet-sum-in-array/0)

**天真的方法**：在此方法中，我们简单地运行三个循环，然后一个接一个地添加三个元素，如果三个元素的和更大，则与先前的和进行比较，然后存储在先前的和中。

## C++ 

```

// 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 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

```

# 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# 

```

// 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 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\. 
?> 

```

**Output :**

```
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 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

```

# 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 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 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

```

# 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 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\. 
?> 

```

**Output :**

```
18

```

**时间复杂度**： O（n）
**空间复杂度**： O（1）

现在不要停下来，将您的学习提高到一个新的水平。 借助最受信任的课程，学习数据结构和算法的所有重要概念： [DSA Self Paced](https://practice.geeksforgeeks.org/courses/dsa-self-paced?utm_source=geeksforgeeks&utm_medium=article&utm_campaign=gfg_article_dsa_content_bottom) 。 以对学生友好的价格准备好行业。

* * *

* * *

如果您喜欢 GeeksforGeeks 并希望做出贡献，则还可以使用 [tribution.geeksforgeeks.org](https://contribute.geeksforgeeks.org/) 撰写文章，或将您的文章邮寄至 tribution@geeksforgeeks.org。 查看您的文章出现在 GeeksforGeeks 主页上，并帮助其他 Geeks。

如果您发现任何不正确的地方，请单击下面的“改进文章”按钮，以改进本文。