Dada una array de enteros positivos de tamaño n. Encuentre la suma máxima del triplete ( a i + a j + a k ) tal que 0 <= i < j < k < n y a i < a j < a k .
Input: a[] = 2 5 3 1 4 9 Output: 16 Explanation: All possible triplets are:- 2 3 4 => sum = 9 2 5 9 => sum = 16 2 3 9 => sum = 14 3 4 9 => sum = 16 1 4 9 => sum = 14 Maximum sum = 16
El enfoque simple es recorrer cada triplete con tres ‘for loops’ anidados y encontrar la actualización de la suma de todos los tripletes uno por uno. La complejidad temporal de este enfoque es O(n 3 ), que no es suficiente para un valor mayor de ‘n’.
Un mejor enfoque es hacer una mayor optimización en el enfoque anterior. En lugar de atravesar cada triplete con tres bucles anidados, podemos atravesar dos bucles anidados. Mientras recorre cada número (asumir como elemento central (a j )), encuentre el número máximo (a i ) más pequeño que un j que lo precede y el número máximo ( ak ) mayor que un j más allá. Ahora, después de eso, actualice la respuesta máxima con la suma calculada de a i + a j + a k
C++
// C++ program to find maximum triplet sum
#include <bits/stdc++.h>
using namespace std;
// Function to calculate maximum triplet sum
int maxTripletSum(int arr[], int n)
{
// Initialize the answer
int ans = 0;
for (int i = 1; i < n - 1; ++i) {
int max1 = 0, max2 = 0;
// find maximum value(less than arr[i])
// from 0 to i-1
for (int j = 0; j < i; ++j)
if (arr[j] < arr[i])
max1 = max(max1, arr[j]);
// find maximum value(greater than arr[i])
// from i+1 to n-1
for (int j = i + 1; j < n; ++j)
if (arr[j] > arr[i])
max2 = max(max2, arr[j]);
// store maximum answer
if(max1 && max2)
ans=max(ans,max1+arr[i]+max2);
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 2, 5, 3, 1, 4, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxTripletSum(arr, n);
return 0;
}
Java
// Java program to find maximum triplet sum
import java.io.*;
import java.math.*;
class GFG {
// Function to calculate maximum triplet sum
static int maxTripletSum(int arr[], int n)
{
// Initialize the answer
int ans = 0;
for (int i = 1; i < n - 1; ++i) {
int max1 = 0, max2 = 0;
// find maximum value(less than arr[i])
// from 0 to i-1
for (int j = 0; j < i; ++j)
if (arr[j] < arr[i])
max1 = Math.max(max1, arr[j]);
// find maximum value(greater than arr[i])
// from i+1 to n-1
for (int j = i + 1; j < n; ++j)
if (arr[j] > arr[i])
max2 = Math.max(max2, arr[j]);
// store maximum answer
if(max1 > 0 && max2 > 0)
ans = Math.max(ans, max1 + arr[i] + max2);
}
return ans;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 2, 5, 3, 1, 4, 9 };
int n = arr.length;
System.out.println(maxTripletSum(arr, n));
}
}
// This code is contributed by Nikita Tiwari.
Python3
# Python 3 program to # find maximum triplet sum # Function to calculate # maximum triplet sum def maxTripletSum(arr, n): # Initialize the answer ans = 0 for i in range(1, (n - 1)): max1 = 0 max2 = 0 # find maximum value(less than arr[i]) # from 0 to i-1 for j in range(0, i): if (arr[j] < arr[i]): max1 = max(max1, arr[j]) # find maximum value(greater than arr[i]) # from i + 1 to n-1 for j in range((i + 1), n): if (arr[j] > arr[i]): max2 = max(max2, arr[j]) # store maximum answer if (max1 > 0 and max2 >0): ans = max(ans, max1 + arr[i] + max2) return ans # Driver code arr = [2, 5, 3, 1, 4, 9] n = len(arr) print(maxTripletSum(arr, n)) # This code is contributed # by Nikita Tiwari.
C#
// C# program to find maximum triplet sum
using System;
class GFG {
// Function to calculate maximum triplet sum
static int maxTripletSum(int[] arr, int n)
{
// Initialize the answer
int ans = 0;
for (int i = 1; i < n - 1; ++i)
{
int max1 = 0, max2 = 0;
// find maximum value(less than
// arr[i]) from 0 to i-1
for (int j = 0; j < i; ++j)
if (arr[j] < arr[i])
max1 = Math.Max(max1, arr[j]);
// find maximum value(greater than
// arr[i]) from i+1 to n-1
for (int j = i + 1; j < n; ++j)
if (arr[j] > arr[i])
max2 = Math.Max(max2, arr[j]);
// store maximum answer
if(max1 > 0 && max2 > 0)
ans = Math.Max(ans, max1 + arr[i] + max2);
}
return ans;
}
// Driver code
public static void Main()
{
int[] arr = { 2, 5, 3, 1, 4, 9 };
int n = arr.Length;
Console.WriteLine(maxTripletSum(arr, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find maximum triplet sum
// Function to calculate maximum triplet sum
function maxTripletSum($arr, $n)
{
// Initialize the answer
$ans = 0;
for ($i = 1; $i < $n - 1; ++$i)
{
$max1 = 0; $max2 = 0;
// find maximum value(less than
// arr[i]) from 0 to i-1
for ($j = 0; $j < $i; ++$j)
if ($arr[$j] < $arr[$i])
$max1 = max($max1, $arr[$j]);
// find maximum value(greater than
// arr[i]) from i+1 to n-1
for ($j = $i + 1; $j < $n; ++$j)
if ($arr[$j] > $arr[$i])
$max2 = max($max2, $arr[$j]);
// store maximum answer
if($max1 && $max2)
$ans = max($ans, $max1 + $arr[$i] + $max2);
}
return $ans;
}
// Driver code
$arr = array(2, 5, 3, 1, 4, 9);
$n = sizeof($arr);
echo maxTripletSum($arr, $n);
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// JavaScript program to find maximum triplet sum
// Function to calculate maximum triplet sum
function maxTripletSum(arr, n)
{
// Initialize the answer
let ans = 0;
for (let i = 1; i < n - 1; ++i) {
let max1 = 0, max2 = 0;
// find maximum value(less than arr[i])
// from 0 to i-1
for (let j = 0; j < i; ++j)
if (arr[j] < arr[i])
max1 = Math.max(max1, arr[j]);
// find maximum value(greater than arr[i])
// from i+1 to n-1
for (let j = i + 1; j < n; ++j)
if (arr[j] > arr[i])
max2 = Math.max(max2, arr[j]);
// store maximum answer
if(max1 && max2)
ans=Math.max(ans,max1+arr[i]+max2);
}
return ans;
}
// Driver code
let arr = [ 2, 5, 3, 1, 4, 9 ];
let n = arr.length;
document.write(maxTripletSum(arr, n));
// This code is contributed by Surbhi Tyagi.
</script>
Producción :
16
Complejidad temporal: O(n 2 )
Espacio auxiliar: O(1)
El mejor y más eficiente enfoque es utilizar el concepto de array máxima de sufijos y búsqueda binaria.
- Para encontrar un número máximo mayor que el número dado más allá de él, podemos mantener una array de sufijos máxima tal que para cualquier número (sufijo i ) contenga el número máximo del índice i, i+1, … n-1. La array de sufijos se puede calcular en tiempo O(n).
- Para encontrar el número máximo más pequeño que el número dado que lo precede, podemos mantener una lista ordenada de números antes de un número dado, de modo que simplemente podamos realizar una búsqueda binaria para encontrar un número que sea más pequeño que el número dado. En el lenguaje C++, podemos realizar esto utilizando el contenedor asociativo establecido de la biblioteca STL.
C++
// C++ program to find maximum triplet sum
#include <bits/stdc++.h>
using namespace std;
// Utility function to get the lower last min
// value of 'n'
int getLowValue(set<int>& lowValue, int& n)
{
auto it = lowValue.lower_bound(n);
// Since 'lower_bound' returns the first
// iterator greater than 'n', thus we
// have to decrement the pointer for
// getting the minimum value
--it;
return (*it);
}
// Function to calculate maximum triplet sum
int maxTripletSum(int arr[], int n)
{
// Initialize suffix-array
int maxSuffArr[n + 1];
// Set the last element
maxSuffArr[n] = 0;
// Calculate suffix-array containing maximum
// value for index i, i+1, i+2, ... n-1 in
// arr[i]
for (int i = n - 1; i >= 0; --i)
maxSuffArr[i] = max(maxSuffArr[i + 1], arr[i]);
int ans = 0;
// Initialize set container
set<int> lowValue;
// Insert minimum value for first comparison
// in the set
lowValue.insert(INT_MIN);
for (int i = 0; i < n - 1; ++i) {
if (maxSuffArr[i + 1] > arr[i]) {
ans = max(ans, getLowValue(lowValue,
arr[i])
+ arr[i] + maxSuffArr[i + 1]);
// Insert arr[i] in set<> for further
// processing
lowValue.insert(arr[i]);
}
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 2, 5, 3, 1, 4, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxTripletSum(arr, n);
return 0;
}
Java
// Java program to find maximum triplet sum
import java.io.*;
import java.util.*;
class GFG{
// Function to calculate maximum triplet sum
public static int maxTripletSum(int arr[], int n)
{
// Initialize suffix-array
int maxSuffArr[] = new int[n + 1];
// Set the last element
maxSuffArr[n] = 0;
// Calculate suffix-array containing maximum
// value for index i, i+1, i+2, ... n-1 in
// arr[i]
for(int i = n - 1; i >= 0; --i)
maxSuffArr[i] = Math.max(maxSuffArr[i + 1],
arr[i]);
int ans = 0;
// Initialize set container
TreeSet<Integer> lowValue = new TreeSet<Integer>();
// Insert minimum value for first comparison
// in the set
lowValue.add(Integer.MIN_VALUE);
for(int i = 0; i < n - 1; ++i)
{
if (maxSuffArr[i + 1] > arr[i])
{
ans = Math.max(ans, lowValue.lower(arr[i]) +
arr[i] + maxSuffArr[i + 1]);
// Insert arr[i] in set<> for further
// processing
lowValue.add(arr[i]);
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 5, 3, 1, 4, 9 };
int n = 6;
System.out.println(maxTripletSum(arr, n));
}
}
// This code is contributed by Manu Pathria
Producción:
16
Complejidad temporal: O(n*log(n))
Espacio auxiliar: O(n)
Este artículo es una contribución de Shubham Bansal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeksorg. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA