Dada una array, la tarea es encontrar la suma máxima de tripletes en la array.
Ejemplos:
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
Enfoque ingenuo: en este método, simplemente ejecutamos tres bucles y uno por uno agregamos tres elementos y comparamos con la suma anterior si la suma de tres elementos es mayor que la almacenada en la suma anterior.
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
// 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.
?>
Javascript
<script>
// JavaScript Program to find maximum triplet sum
function maxTripletSum(arr, n)
{
// Initialize sum with INT_MIN
let sum = -1000000;
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
for (let 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
let arr = [ 1, 0, 8, 6, 4, 2 ];
let n = arr.length;
document.write(maxTripletSum(arr, n));
</script>
// This code is contributed by sanjoy_62.
Producción:
18
Complejidad de tiempo: O (n ^ 3)
Complejidad de espacio: O (1)
Otro enfoque: en esto, primero debemos ordenar toda la array y luego, cuando agregamos los últimos tres elementos de la array, encontramos la suma máxima de trillizos.
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.
?>
Javascript
<script>
//Javascript 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
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
let arr = [ 1, 0, 8, 6, 4, 2 ];
let n = arr.length;
document.write(maxTripletSum(arr, n));
// This code is contributed by Mayank Tyagi
</script>
Producción:
18
Complejidad de tiempo: O(nlogn)
Complejidad de espacio: O(1)
Enfoque eficiente: escanee la array y calcule el máximo, el segundo máximo y el tercer elemento máximo presentes en la array y devuelva la suma de sus y sería la suma máxima.
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.
?>
Javascript
<script>
// JavaScript 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
let maxA = Number.MIN_SAFE_INTEGER;
let maxB = Number.MIN_SAFE_INTEGER;
let maxC = Number.MIN_SAFE_INTEGER;
for (let 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
let arr = [ 1, 0, 8, 6, 4, 2 ];
let n = arr.length;
document.write(maxTripletSum(arr, n));
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
18
Complejidad temporal : O(n)
Complejidad espacial : O(1)
Publicación traducida automáticamente
Artículo escrito por SHARIQ_JMI y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA