El triplete lexicográfico más grande de una array dada que forma un triángulo

Dado un arreglo arr[] , la tarea es encontrar el triplete lexicográficamente más grande en ese arreglo que pueda formar un triángulo. Si no existe tal triplete, imprima -1 .
Ejemplo: 
 

Entrada: arr[] = { 4, 2, 10, 3, 5 } 
Salida: 3 4 5 
Explicación: 
El triplete lexicográficamente más grande es (4, 5, 10). Pero no forma un triángulo. 
El siguiente triplete lexicográficamente más grande es (3, 4, 5). 
Como forma un triángulo, es la respuesta requerida.
Entrada: arr[] = { 20, 12, 120, 3, 15 } 
Salida: 12 15 20 
 

Enfoque: 
Un triplete puede formar un triángulo si y solo si sigue la condición dada a continuación: 
 

Si A, B y C forman un triplete, entonces el triplete puede formar un triángulo si 
A < B + C o B < A + C o C < A + B 
 

La idea es usar Sorting . Ordene la array en orden ascendente. Comience a atravesar desde el final de la array y verifique si algún triplete satisface la condición anterior. Imprima el primer triplete para satisfacer la condición, como salida. Si no se puede encontrar tal triplete, imprima -1 .
A continuación se muestra la implementación del enfoque anterior:

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find lexicographically
// largest triplet that forms a
// triangle in the given array
void findTriplet(int arr[], int N)
{
 
    // Sort the array
    sort(arr, arr + N);
 
    int flag = 0, i;
 
    // Iterate from the end of the array
    for (i = N - 1; i - 2 >= 0; i--) {
 
        // If the triplet forms a triangle
        if (arr[i - 2] + arr[i - 1] > arr[i]) {
            flag = 1;
            break;
        }
    }
 
    // If triplet found
    if (flag) {
 
        // Print the triplet
        cout << arr[i - 2] << " "
             << arr[i - 1] << " "
             << arr[i] << endl;
    }
 
    // Otherwise
    else {
        cout << -1 << endl;
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 4, 2, 10, 3, 5 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    findTriplet(arr, N);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
     
// Function to find lexicographically
// largest triplet that forms a
// triangle in the given array
static void findTriplet(int arr[], int N)
{
     
    // Sort the array
    Arrays.sort(arr);
 
    int flag = 0, i;
 
    // Iterate from the end of the array
    for(i = N - 1; i - 2 >= 0; i--)
    {
         
        // If the triplet forms a triangle
        if (arr[i - 2] + arr[i - 1] > arr[i])
        {
            flag = 1;
            break;
        }
    }
 
    // If triplet found
    if (flag != 0)
    {
         
        // Print the triplet
        System.out.println(arr[i - 2] + " " +
                           arr[i - 1] + " " +
                           arr[i] );
    }
 
    // Otherwise
    else
    {
        System.out.println(-1);
    }
}
 
// Driver Code
public static void main (String []args)
{
    int arr[] = { 4, 2, 10, 3, 5 };
 
    int N = arr.length;
 
    findTriplet(arr, N);
}
}
 
// This code is contributed by chitranayal

# Python3 implementation of
# the above approach
 
# Function to find lexicographically
# largest triplet that forms a
# triangle in the given array
def findTriplet(arr, N):
 
    # Sort the array
    arr.sort()
 
    # Iterate from the end of the array
    i = N - 1
    while i - 2 >= 0:
 
        # If the triplet forms a triangle
        if(arr[i - 2] + arr[i - 1] > arr[i]):
            flag = 1
            break
 
        i -= 1
 
    # If triplet found
    if(flag):
 
        # Print the triplet
        print(arr[i - 2],
              arr[i - 1],
              arr[i])
 
    # Otherwise
    else:
        print(-1)
 
# Driver Code
if __name__ == '__main__':
 
    arr = [ 4, 2, 10, 3, 5 ]
 
    N = len(arr)
 
    findTriplet(arr, N)
 
# This code is contributed by Shivam Singh

// C# program to implement
// the above approach
using System;
class GFG{
     
// Function to find lexicographically
// largest triplet that forms a
// triangle in the given array
static void findTriplet(int []arr, int N)
{
     
    // Sort the array
    Array.Sort(arr);
 
    int flag = 0, i;
 
    // Iterate from the end of the array
    for(i = N - 1; i - 2 >= 0; i--)
    {
         
        // If the triplet forms a triangle
        if (arr[i - 2] + arr[i - 1] > arr[i])
        {
            flag = 1;
            break;
        }
    }
 
    // If triplet found
    if (flag != 0)
    {
         
        // Print the triplet
        Console.Write(arr[i - 2] + " " +
                      arr[i - 1] + " " +
                      arr[i] );
    }
 
    // Otherwise
    else
    {
        Console.Write(-1);
    }
}
 
// Driver Code
public static void Main (string []args)
{
    int []arr = { 4, 2, 10, 3, 5 };
 
    int N = arr.Length;
 
    findTriplet(arr, N);
}
}
 
// This code is contributed by Ritik Bansal

<script>
 
      // JavaScript Program to implement
      // the above approach
      // Function to find lexicographically
      // largest triplet that forms a
      // triangle in the given array
      function findTriplet(arr, N) {
        // Sort the array
        arr.sort((a, b) => a - b);
 
        var flag = 0,
          i;
 
        // Iterate from the end of the array
        for (i = N - 1; i - 2 >= 0; i--) {
          // If the triplet forms a triangle
          if (arr[i - 2] + arr[i - 1] > arr[i]) {
            flag = 1;
            break;
          }
        }
 
        // If triplet found
        if (flag) {
          // Print the triplet
          document.write(
            arr[i - 2] +
              "  " +
              arr[i - 1] +
              "  " +
              arr[i] +
              "<br>"
          );
        }
 
        // Otherwise
        else {
          document.write(-1 + "<br>");
        }
      }
 
      // Driver Code
      var arr = [4, 2, 10, 3, 5];
      var N = arr.length;
      findTriplet(arr, N);
       
</script>

3 4 5

Complejidad de tiempo: O(N*log(N)) 
Espacio auxiliar: O(1)