Valor máximo de la expresión (arr[i] + arr[j] * arr[k]) formada a partir de un triplete válido

Dada una array  arr[] de N enteros. La tarea es encontrar el valor máximo de (arr[i] + arr[j] * arr[k]) entre cada triplete (i, j, k) tal que arr[i] < arr[j] < arr[k ] y yo < j < k . Si no existe ninguno de esos tripletes, imprima «-1» .

Ejemplos:

Entrada: arr[]={7, 9, 3, 8, 11, 10}
Salida: 106
Explicación:
Los tripletes válidos son:
1) (7, 9, 11) y el valor de (arr[i] + arr[ j] * arr[k]) es 106.
2) (7, 9, 10), y el valor de (arr[i] + arr[j] * arr[k]) es 97.
3) (7, 8, 10), y el valor de (arr[i] + arr[j] * arr[k]) es 87.
4) (7, 8, 11), y el valor de (arr[i] + arr[j] * arr [k]) es 105.
5) (3, 8, 10), y el valor de (arr[i] + arr[j] * arr[k]) es 83.
6) (3, 8, 11), y el valor de (arr[i] + arr[j] * arr[k]) es 91.
Por lo tanto, el máximo entre los valores es 106

Entrada: arr[]={1, 2, 3}
Salida: 7

Enfoque ingenuo: la idea es generar todos los tripletes válidos posibles (i, j, k) e imprimir el valor máximo de arr[i] + arr[j]*arr[k] entre todos los tripletes. A continuación se muestran los pasos:

1. Iterar sobre la array usando tres bucles anidados.
2. Para cada triplete válido, compruebe si arr[i] < arr[j] < arr[k] . Si es así, entonces el triplete es válido.
3. Encuentre el valor de arr[i] + arr[j]*arr[k] para todos esos tripletes si la condición anterior es verdadera y guárdelo en la variable llamada value .
4. Continúe actualizando el valor de la expresión anterior al valor máximo entre todos los tripletes posibles.
5. Si no se encuentra un triplete válido, imprima -1 De lo contrario, imprima el valor máximo.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that generate all valid
// triplets and calculate the value
// of the valid triplets
void max_valid_triplet(int A[], int n)
{
    int ans = -1;
 
    // Generate all triplets
    for(int i = 0; i < n - 2; i++)
    {
        for(int j = i + 1; j < n - 1; j++)
        {
            for(int k = j + 1; k < n; k++)
            {
                 
                // Check whether the triplet
                // is valid or not
                if (A[i] < A[j] && A[j] < A[k])
                {
                    int value = A[i] + A[j] * A[k];
 
                    // Update the value
                    if (value > ans)
                    {
                        ans = value;
                    }
                }
            }
        }
    }
     
    // Print the maximum value
    cout << (ans);
}
 
// Driver Code
int main()
{
     
    // Given array arr[]
    int arr[] = { 7, 9, 3, 8, 11, 10 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    max_valid_triplet(arr, n);
    return 0;
}
 
// This code is contributed by chitranayal

// Java program for the above approach
import java.util.Scanner;
 
class GFG {
 
    // Function that generate all valid
    // triplets and calculate the value
    // of the valid triplets
    static void
    max_valid_triplet(int A[], int n)
    {
 
        int ans = -1;
 
        // Generate all triplets
        for (int i = 0; i < n - 2; i++) {
 
            for (int j = i + 1; j < n - 1; j++) {
 
                for (int k = j + 1; k < n; k++) {
 
                    // Check whether the triplet
                    // is valid or not
                    if (A[i] < A[j] && A[j] < A[k]) {
 
                        int value = A[i] + A[j] * A[k];
 
                        // Update the value
                        if (value > ans) {
                            ans = value;
                        }
                    }
                }
            }
        }
 
        // Print the maximum value
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String args[])
    {
        // Given array arr[]
        int[] arr = new int[] { 7, 9, 3, 8, 11, 10 };
 
        int n = arr.length;
 
        // Function Call
        max_valid_triplet(arr, n);
    }
}

# Python3 program for the above approach
 
# Function that generate all valid
# triplets and calculate the value
# of the valid triplets
def max_valid_triplet(A, n):
 
    ans = -1;
 
    # Generate all triplets
    for i in range(0, n - 2):
        for j in range(i + 1, n - 1):
            for k in range(j + 1, n):
 
                # Check whether the triplet
                # is valid or not
                if (A[i] < A[j] and A[j] < A[k]):
                    value = A[i] + A[j] * A[k];
 
                    # Update the value
                    if (value > ans):
                        ans = value;
                     
    # Print the maximum value
    print(ans);
 
# Driver Code
if __name__ == '__main__':
     
    # Given array arr
    arr = [ 7, 9, 3, 8, 11, 10 ];
 
    n = len(arr);
 
    # Function call
    max_valid_triplet(arr, n);
 
# This code is contributed by Amit Katiyar 

// C# program for the above approach
using System;
class GFG{
 
  // Function that generate all valid
  // triplets and calculate the value
  // of the valid triplets
  static void max_valid_triplet(int[] A, int n)
  {
    int ans = -1;
 
    // Generate all triplets
    for (int i = 0; i < n - 2; i++)
    {
      for (int j = i + 1; j < n - 1; j++)
      {
        for (int k = j + 1; k < n; k++)
        {
 
          // Check whether the triplet
          // is valid or not
          if (A[i] < A[j] && A[j] < A[k])
          {
            int value = A[i] + A[j] * A[k];
 
            // Update the value
            if (value > ans)
            {
              ans = value;
            }
          }
        }
      }
    }
 
    // Print the maximum value
    Console.WriteLine(ans);
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    // Given array []arr
    int[] arr = new int[] { 7, 9, 3, 8, 11, 10 };
 
    int n = arr.Length;
 
    // Function Call
    max_valid_triplet(arr, n);
  }
}
 
// This code is contributed by gauravrajput1

<script>
// JavaScript program for the above approach
 
// Function that generate all valid
// triplets and calculate the value
// of the valid triplets
function max_valid_triplet(A, n)
{
    let ans = -1;
 
    // Generate all triplets
    for(let i = 0; i < n - 2; i++)
    {
        for(let j = i + 1; j < n - 1; j++)
        {
            for(let k = j + 1; k < n; k++)
            {
                 
                // Check whether the triplet
                // is valid or not
                if (A[i] < A[j] && A[j] < A[k])
                {
                    let value = A[i] + A[j] * A[k];
 
                    // Update the value
                    if (value > ans)
                    {
                        ans = value;
                    }
                }
            }
        }
    }
     
    // Print the maximum value
    document.write(ans);
}
 
// Driver Code
 
    // Given array arr[]
    let arr = [ 7, 9, 3, 8, 11, 10 ];
    let n = arr.length;
 
    // Function call
    max_valid_triplet(arr, n);
 
// This code is contributed by Surbhi Tyagi.
</script>

106

Complejidad de Tiempo: O(N ³ )
Espacio Auxiliar: O(1)

Enfoque eficiente: el método anterior se puede optimizar utilizando TreeSet en Java . A continuación se muestran los pasos:

• Crea dos arrays. Una array (izquierda) para almacenar el elemento máximo en el lado izquierdo que es estrictamente menor que el elemento presente en la array original y otra array (derecha) para almacenar el máximo en el lado derecho del elemento presente en la array original como se muestra a continuación imagen para array arr[] = {7, 9, 3, 8, 11, 10} : 
   

• Para la construcción de la array izquierda, usamos TreeSet en Java, insertamos los elementos en TreeSet, usamos el método lower() en TreeSet que devolverá el elemento más grande en este conjunto, que es estrictamente menor que el elemento dado. Si no existe tal elemento en esta colección TreeSet, este método devuelve NULL.
• Los elementos del arreglo izquierdo serán arr[i] de los tripletes válidos y los elementos del arreglo derecho serán arr[k] del triplete válido.
• Ahora, recorra la array original de 1 a N – 1 , para seleccionar arr[j] para el triplete válido.
• Si left[i]!=-1 && right[i]!=-1 entonces existe la posibilidad de formar un triplete.
• Encuentre el valor arr[i] + arr[j]*arr[k] para todos esos tripletes válidos y actualice el ans según el valor máximo.
• Imprime el valor máximo si existe, de lo contrario imprime “-1” .

A continuación se muestra la implementación del enfoque anterior:

// Java program for the above approach
import java.util.*;
 
class GFG {
 
    // Function that finds the maximum
    // valid triplets
    static int max_valid_triplet(int A[], int n)
    {
        int ans = -1;
 
        // Declare the left[] and
        // right[] array
        int left[] = new int[n];
        int right[] = new int[n];
 
        // Consider last element as maximum
        int max = A[n - 1];
 
        // Iterate array from the last
        for (int i = n - 2; i >= 0; i--) {
 
            // If present is less the maximum
            // update the right[i] with
            // previous maximum
            if (max > A[i])
                right[i] = max;
 
            // Else store -1
            else
                right[i] = -1;
 
            // Find the maximum for
            // the next iteration
            if (max < A[i])
                max = A[i];
        }
 
        TreeSet<Integer> set = new TreeSet<Integer>();
        for (int i = 1; i < n; i++) {
 
            // Insert previous element
            // to the set
            set.add(A[i - 1]);
 
            Integer result = set.lower(A[i]);
 
            // Search for maximum element
            // which is < present element
 
            // If result is null there is
            // no such element exists
            // so store -1 at left[i]
            if (result == null)
                left[i] = -1;
 
            // Else store the result
            else
                left[i] = result;
        }
 
        // Traverse the original array
        for (int i = 1; i < n - 1; i++) {
 
            // Condition for valid triplet
            if (left[i] != -1
                && right[i] != -1)
 
                // Find the value and update
                // the maximum value
                ans = Math.max(ans,
                               left[i] + A[i] * right[i]);
        }
 
        // Return the ans
        return ans;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        // Given array arr[]
        int[] A = new int[] { 7, 9, 3, 8, 11, 10 };
        int n = A.length;
 
        // Function Call
        System.out.println(max_valid_triplet(A, n));
    }
}

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function that finds the maximum
// valid triplets
static int max_valid_triplet(int []A, int n)
{
    int ans = -1;
 
    // Declare the []left and
    // []right array
    int []left = new int[n];
    int []right = new int[n];
 
    // Consider last element as maximum
    int max = A[n - 1];
 
    // Iterate array from the last
    for(int i = n - 2; i >= 0; i--)
    {
         
        // If present is less the maximum
        // update the right[i] with
        // previous maximum
        if (max > A[i])
            right[i] = max;
 
        // Else store -1
        else
            right[i] = -1;
 
        // Find the maximum for
        // the next iteration
        if (max < A[i])
            max = A[i];
    }
 
    SortedSet<int> set = new SortedSet<int>();
    for(int i = 1; i < n; i++)
    {
         
        // Insert previous element
        // to the set
        set.Add(A[i - 1]);
 
        int result = set.Min;
 
        // Search for maximum element
        // which is < present element
 
        // If result is null there is
        // no such element exists
        // so store -1 at left[i]
        if (result == 0)
            left[i] = -1;
 
        // Else store the result
        else
            left[i] = result;
    }
 
    // Traverse the original array
    for(int i = 1; i < n - 1; i++)
    {
         
        // Condition for valid triplet
        if (left[i] != -1 &&
           right[i] != -1)
 
            // Find the value and update
            // the maximum value
            ans = Math.Max(ans,
                           left[i] +
                              A[i] *
                          right[i]);
    }
 
    // Return the ans
    return ans;
}
 
// Driver Code
public static void Main(String []args)
{
     
    // Given array []arr
    int[] A = new int[]{ 7, 9, 3, 8, 11, 10 };
    int n = A.Length;
 
    // Function call
    Console.WriteLine(max_valid_triplet(A, n));
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// Javascript program for the above approach
 
// Function that finds the maximum
// valid triplets
function max_valid_triplet(A, n)
{
    let ans = -1;
  
    // Declare the []left and
    // []right array
    let left = new Array(n);
       let right = new Array(n);
        
     for(let i = 0; i < n; i++)
    {
        left[i] = 0;
        right[i] = 0;
    }
     
    // Consider last element as maximum
    let max = A[n - 1];
  
    // Iterate array from the last
    for(let i = n - 2; i >= 0; i--)
    {
         
        // If present is less the maximum
        // update the right[i] with
        // previous maximum
        if (max > A[i])
            right[i] = max;
  
        // Else store -1
        else
            right[i] = -1;
  
        // Find the maximum for
        // the next iteration
        if (max < A[i])
            max = A[i];
    }
  
    let set = new Set();
    for(let i = 1; i < n; i++)
    {
          
        // Insert previous element
        // to the set
        set.add(A[i - 1]);
  
        let result = Math.min(...Array.from(set));
  
        // Search for maximum element
        // which is < present element
  
        // If result is null there is
        // no such element exists
        // so store -1 at left[i]
        if (result == 0)
            left[i] = -1;
  
        // Else store the result
        else
            left[i] = result;
    }
  
    // Traverse the original array
    for(let i = 1; i < n - 1; i++)
    {
         
        // Condition for valid triplet
        if (left[i] != -1 &&
           right[i] != -1)
  
            // Find the value and update
            // the maximum value
            ans = Math.max(ans, left[i] +
                           A[i] * right[i]);
    }
  
    // Return the ans
    return ans;
}
 
// Driver Code
let A = [ 7, 9, 3, 8, 11, 10 ];
let n = A.length;
 
document.write(max_valid_triplet(A, n));
 
// This code is contributed by avanitrachhadiya2155
 
</script>

106

Complejidad temporal: O(N)
Espacio auxiliar: O(N)