Rectángulo de área máxima seleccionando cuatro lados de la array

Dada una array de n enteros positivos que representan longitudes. Averigüe el área máxima posible cuyos cuatro lados se eligen de una array dada. Tenga en cuenta que solo se puede formar un rectángulo si hay dos pares de valores iguales en una array dada.

Ejemplos: 

Input : arr[] = {2, 1, 2, 5, 4, 4}
Output : 8
Explanation : Dimension will be 4 * 2

Input : arr[] = {2, 1, 3, 5, 4, 4}
Output : 0
Explanation : No rectangle possible

Método 1 (Clasificación): la tarea básicamente se reduce a encontrar dos pares de valores iguales en una array. Si hay más de dos pares, elija los dos pares con valores máximos. Una solución simple es hacer lo siguiente. 

1. Ordenar la array dada. 
2. Atraviese la array desde el valor más grande al más pequeño y devuelva dos pares con valores máximos.

Implementación:

// CPP program for finding maximum area possible
// of a rectangle
#include <bits/stdc++.h>
using namespace std;
 
// function for finding max area
int findArea(int arr[], int n)
{
    // sort array in non-increasing order
    sort(arr, arr + n, greater<int>());
 
    // Initialize two sides of rectangle
    int dimension[2] = { 0, 0 };
 
    // traverse through array
    for (int i = 0, j = 0; i < n - 1 && j < 2; i++)
 
        // if any element occurs twice
        // store that as dimension
        if (arr[i] == arr[i + 1])
            dimension[j++] = arr[i++];
 
    // return the product of dimensions
    return (dimension[0] * dimension[1]);
}
 
// driver function
int main()
{
    int arr[] = { 4, 2, 1, 4, 6, 6, 2, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findArea(arr, n);
    return 0;
}

// Java program for finding maximum area
// possible of a rectangle
import java.util.Arrays;
import java.util.Collections;
 
public class GFG
{    
    // function for finding max area
    static int findArea(Integer arr[], int n)
    {
        // sort array in non-increasing order
        Arrays.sort(arr, Collections.reverseOrder());
      
        // Initialize two sides of rectangle
        int[] dimension = { 0, 0 };
      
        // traverse through array
        for (int i = 0, j = 0; i < n - 1 && j < 2;
                                           i++)
      
            // if any element occurs twice
            // store that as dimension
            if (arr[i] == arr[i + 1])
                dimension[j++] = arr[i++];
      
        // return the product of dimensions
        return (dimension[0] * dimension[1]);
    }
      
    // driver function
    public static void main(String args[])
    {
        Integer arr[] = { 4, 2, 1, 4, 6, 6, 2, 5 };
        int n = arr.length;
        System.out.println(findArea(arr, n));
    }
}
// This code is contributed by Sumit Ghosh

# Python3 program for finding
# maximum area possible of
# a rectangle
 
# function for finding
# max area
def findArea(arr, n):
 
    # sort array in
    # non-increasing order
    arr.sort(reverse = True)
 
    # Initialize two
    # sides of rectangle
    dimension = [0, 0]
 
    # traverse through array
    i = 0
    j = 0
    while(i < n - 1 and j < 2):
 
        # if any element occurs twice
        # store that as dimension
        if (arr[i] == arr[i + 1]):
            dimension[j] = arr[i]
            j += 1
            i += 1
        i += 1
         
    # return the product
    # of dimensions
    return (dimension[0] *
            dimension[1])
 
# Driver code
arr = [4, 2, 1, 4, 6, 6, 2, 5]
n = len(arr)
print(findArea(arr, n))
 
# This code is contributed
# by Smitha

// C# program for finding maximum area
// possible of a rectangle
using System;
using System.Collections;
 
class GFG
{
// function for finding max area
static int findArea(int []arr, int n)
{
    // sort array in non-increasing order
    Array.Sort(arr);
    Array.Reverse(arr);
 
    // Initialize two sides of rectangle
    int[] dimension = { 0, 0 };
 
    // traverse through array
    for (int i = 0, j = 0;
             i < n - 1 && j < 2; i++)
 
        // if any element occurs twice
        // store that as dimension
        if (arr[i] == arr[i + 1])
            dimension[j++] = arr[i++];
 
    // return the product of dimensions
    return (dimension[0] * dimension[1]);
}
 
// Driver Code
public static void Main(String []args)
{
    int []arr = { 4, 2, 1, 4, 6, 6, 2, 5 };
    int n = arr.Length;
    Console.Write(findArea(arr, n));
}
}
 
// This code is contributed
// by PrinciRaj1992

<?php
// PHP program for finding maximum area possible
// of a rectangle
 
// function for finding max area
function findArea($arr, $n)
{
     
    // sort array in non-
    // increasing order
    rsort($arr);
 
    // Initialize two sides
    // of rectangle
    $dimension = array( 0, 0 );
 
    // traverse through array
    for( $i = 0, $j = 0; $i < $n - 1 &&
                           $j < 2; $i++)
 
        // if any element occurs twice
        // store that as dimension
        if ($arr[$i] == $arr[$i + 1])
            $dimension[$j++] = $arr[$i++];
 
    // return the product
    // of dimensions
    return ($dimension[0] *
            $dimension[1]);
}
 
    // Driver Code
    $arr = array(4, 2, 1, 4, 6, 6, 2, 5);
    $n =count($arr);
    echo findArea($arr, $n);
     
// This code is contributed by anuj_67.
?>

<script>
 
// Javascript program for finding maximum area possible
// of a rectangle
 
// function for finding max area
function findArea(arr, n)
{
    // sort array in non-increasing order
    arr.sort((a,b)=>{return b-a;})
 
    // Initialize two sides of rectangle
    var dimension = [0,0];
 
    // traverse through array
    for (var i = 0, j = 0; i < n - 1 && j < 2; i++)
 
        // if any element occurs twice
        // store that as dimension
        if (arr[i] == arr[i + 1])
            dimension[j++] = arr[i++];
 
    // return the product of dimensions
    return (dimension[0] * dimension[1]);
}
 
// driver function
var arr = [ 4, 2, 1, 4, 6, 6, 2, 5 ];
var n = arr.length;
document.write( findArea(arr, n));
 
</script>

24

Complejidad de tiempo: O (n Log n)

Método 2 (hashing): la idea es insertar todas las primeras apariciones de elementos en un conjunto hash. Para las segundas apariciones, realice un seguimiento de un máximo de dos valores. 

Implementación:

// CPP program for finding maximum area possible
// of a rectangle
#include <bits/stdc++.h>
using namespace std;
 
// function for finding max area
int findArea(int arr[], int n)
{
    unordered_set<int> s;
 
    // traverse through array
    int first = 0, second = 0;
    for (int i = 0; i < n; i++) {
 
        // If this is first occurrence of arr[i],
        // simply insert and continue
        if (s.find(arr[i]) == s.end()) {
            s.insert(arr[i]);
            continue;
        }
 
        // If this is second (or more) occurrence,
        // update first and second maximum values.
        if (arr[i] > first) {
            second = first;
            first = arr[i];
        } else if (arr[i] > second)
            second = arr[i];
    }
 
    // return the product of dimensions
    return (first * second);
}
 
// driver function
int main()
{
    int arr[] = { 4, 2, 1, 4, 6, 6, 2, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findArea(arr, n);
    return 0;
}

// Java program for finding maximum
// area possible of a rectangle
import java.util.HashSet;
import java.util.Set;
 
public class GFG
{    
    // function for finding max area
    static int findArea(int arr[], int n)
    {
        //unordered_set<int> s;
         
        Set<Integer> s = new HashSet<>();
      
        // traverse through array
        int first = 0, second = 0;
        for (int i = 0; i < n; i++) {
      
            // If this is first occurrence of
            // arr[i], simply insert and continue
            if (!s.contains(arr[i])) {
                s.add(arr[i]);
                continue;
            }
      
            // If this is second (or more)
            // occurrence, update first and
            // second maximum values.
            if (arr[i] > first) {
                second = first;
                first = arr[i];
            } else if (arr[i] > second)
                second = arr[i];
        }
      
        // return the product of dimensions
        return (first * second);
    }
      
    // driver function
    public static void main(String args[])
    {
        int arr[] = { 4, 2, 1, 4, 6, 6, 2, 5 };
        int n = arr.length;
        System.out.println(findArea(arr, n));
    }
}
// This code is contributed by Sumit Ghosh

# Python 3 program for finding maximum
# area possible of a rectangle
 
# function for finding max area
def findArea(arr, n):
 
    s = []
 
    # traverse through array
    first = 0
    second = 0
    for i in range(n) :
 
        # If this is first occurrence of
        # arr[i], simply insert and continue
        if arr[i] not in s:
            s.append(arr[i])
            continue
 
        # If this is second (or more) occurrence,
        # update first and second maximum values.
        if (arr[i] > first) :
            second = first
            first = arr[i]
        else if (arr[i] > second):
            second = arr[i]
 
    # return the product of dimensions
    return (first * second)
 
# Driver Code
if __name__ == "__main__":
     
    arr = [ 4, 2, 1, 4, 6, 6, 2, 5 ]
    n = len(arr)
    print(findArea(arr, n))
 
# This code is contributed by ita_c

using System;
using System.Collections.Generic;
 
// c# program for finding maximum 
// area possible of a rectangle
 
public class GFG
{
    // function for finding max area
    public static int findArea(int[] arr, int n)
    {
        //unordered_set<int> s;
 
        ISet<int> s = new HashSet<int>();
 
        // traverse through array
        int first = 0, second = 0;
        for (int i = 0; i < n; i++)
        {
 
            // If this is first occurrence of 
            // arr[i], simply insert and continue
            if (!s.Contains(arr[i]))
            {
                s.Add(arr[i]);
                continue;
            }
 
            // If this is second (or more) 
            // occurrence, update first and 
            // second maximum values.
            if (arr[i] > first)
            {
                second = first;
                first = arr[i];
            }
            else if (arr[i] > second)
            {
                second = arr[i];
            }
        }
 
        // return the product of dimensions
        return (first * second);
    }
 
    // driver function
    public static void Main(string[] args)
    {
        int[] arr = new int[] {4, 2, 1, 4, 6, 6, 2, 5};
        int n = arr.Length;
        Console.WriteLine(findArea(arr, n));
    }
}
 
// This code is contributed by Shrikant13

<script>
 
// Javascript program for finding maximum
// area possible of a rectangle
     
// Function for finding max area
function findArea(arr, n)
{
    let s = new Set();
   
    // Traverse through array
    let first = 0, second = 0;
    for(let i = 0; i < n; i++)
    {
         
        // If this is first occurrence of
        // arr[i], simply insert and continue
        if (!s.has(arr[i]))
        {
            s.add(arr[i]);
            continue;
        }
   
        // If this is second (or more)
        // occurrence, update first and
        // second maximum values.
        if (arr[i] > first)
        {
            second = first;
            first = arr[i];
        }
        else if (arr[i] > second)
            second = arr[i];
    }
   
    // Return the product of dimensions
    return (first * second);
}
 
// Driver Code
let arr = [ 4, 2, 1, 4, 6, 6, 2, 5 ];
let n = arr.length;
 
document.write(findArea(arr, n));
 
// This code is contributed by avanitrachhadiya2155
     
</script>

24

Complejidad de tiempo: O(n)

Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.