Dada una array, la tarea es calcular la suma de todos los rectángulos de área máxima posibles que se pueden formar a partir de los elementos de la array. Además, puede reducir los elementos de la array en 1 como máximo.
Ejemplos:
Input: a = {10, 10, 10, 10, 11,
10, 11, 10}
Output: 210
Explanation:
We can form two rectangles one square (10 * 10)
and one (11 * 10). Hence, total area = 100 + 110 = 210.
Input: a = { 3, 4, 5, 6 }
Output: 15
Explanation:
We can reduce 4 to 3 and 6 to 5 so that we got
rectangle of (3 * 5). Hence area = 15.
Input: a = { 3, 2, 5, 2 }
Output: 0
Enfoque ingenuo: verifique los cuatro elementos posibles de la array y luego cualquiera que pueda formar un rectángulo. En estos rectángulos, separe todos aquellos rectángulos que sean del área máxima formada por estos elementos. Después de obtener los rectángulos y sus áreas, súmalos todos para obtener la solución deseada.
Enfoque eficiente: para obtener el rectángulo de área máxima, primero ordene los elementos de la array en la array no creciente. Después de ordenar, inicie el procedimiento para seleccionar los elementos de la array. Aquí, la selección de dos elementos de la array (como la longitud del rectángulo) es posible si los elementos de la array son iguales (a[i] == a[i+1]) o si la longitud del elemento más pequeño a[i+1] es uno menor que a[i] ( en este caso tenemos nuestra longitud a[i+1] porque a[i] se reduce en 1 ). Se mantiene una variable de bandera para verificar si obtenemos tanto la longitud como la anchura.Después de obtener la longitud, configure la variable de la bandera, ahora calcule la anchura de la misma manera que lo hemos hecho para la longitud y sume el área del rectángulo. Después de obtener tanto el largo como el ancho, vuelva a establecer la variable de la bandera como falsa para que ahora busquemos un nuevo rectángulo. Este proceso se repite y por último se devuelve la suma final del área.
C++
// CPP code to find sum of all
// area rectangle possible
#include <bits/stdc++.h>
using namespace std;
// Function to find
// area of rectangles
int MaxTotalRectangleArea(int a[],
int n)
{
// sorting the array in
// descending order
sort(a, a + n, greater<int>());
// store the final sum of
// all the rectangles area
// possible
int sum = 0;
bool flag = false;
// temporary variable to store
// the length of rectangle
int len;
for (int i = 0; i < n; i++)
{
// Selecting the length of
// rectangle so that difference
// between any two number is 1
// only. Here length is selected
// so flag is set
if ((a[i] == a[i + 1] || a[i] -
a[i + 1] == 1) && (!flag))
{
// flag is set means
// we have got length of
// rectangle
flag = true;
// length is set to
// a[i+1] so that if
// a[i] a[i+1] is less
// than by 1 then also
// we have the correct
// choice for length
len = a[i + 1];
// incrementing the counter
// one time more as we have
// considered a[i+1] element
// also so.
i++;
}
// Selecting the width of rectangle
// so that difference between any
// two number is 1 only. Here width
// is selected so now flag is again
// unset for next rectangle
else if ((a[i] == a[i + 1] ||
a[i] - a[i + 1] == 1) && (flag))
{
// area is calculated for
// rectangle
sum = sum + a[i + 1] * len;
// flag is set false
// for another rectangle
// which we can get from
// elements in array
flag = false;
// incrementing the counter
// one time more as we have
// considered a[i+1] element
// also so.
i++;
}
}
return sum;
}
// Driver code
int main()
{
int a[] = { 10, 10, 10, 10,
11, 10, 11, 10,
9, 9, 8, 8 };
int n = sizeof(a) / sizeof(a[0]);
cout << MaxTotalRectangleArea(a, n);
return 0;
}
Java
// Java code to find sum of
// all area rectangle possible
import java.io.*;
import java.util.Arrays;
import java.util.*;
class GFG
{
// Function to find
// area of rectangles
static int MaxTotalRectangleArea(Integer []a,
int n)
{
// sorting the array in
// descending order
Arrays.sort(a, Collections.reverseOrder());
// store the final sum of
// all the rectangles area
// possible
int sum = 0;
boolean flag = false;
// temporary variable to
// store the length of rectangle
int len = 0;
for (int i = 0; i < n; i++)
{
// Selecting the length of
// rectangle so that difference
// between any two number is 1
// only. Here length is selected
// so flag is set
if ((a[i] == a[i + 1] ||
a[i] - a[i+1] == 1) &&
!flag)
{
// flag is set means
// we have got length of
// rectangle
flag = true;
// length is set to
// a[i+1] so that if
// a[i] a[i+1] is less
// than by 1 then also
// we have the correct
// choice for length
len = a[i+1];
// incrementing the counter
// one time more as we have
// considered a[i+1] element
// also so.
i++;
}
// Selecting the width of rectangle
// so that difference between any
// two number is 1 only. Here width
// is selected so now flag is again
// unset for next rectangle
else if ((a[i] == a[i + 1] ||
a[i] - a[i+1] == 1) &&
(flag))
{
// area is calculated for
// rectangle
sum = sum + a[i+1] * len;
// flag is set false
// for another rectangle
// which we can get from
// elements in array
flag = false;
// incrementing the counter
// one time more as we have
// considered a[i+1] element
// also so.
i++;
}
}
return sum;
}
// Driver code
public static void main (String args[])
{
Integer []a = { 10, 10, 10, 10,
11, 10, 11, 10,
9, 9, 8, 8 };
int n = a.length;
System.out.print(MaxTotalRectangleArea(a, n));
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Python3
# Python3 code to find sum # of all area rectangle # possible # Function to find # area of rectangles def MaxTotalRectangleArea(a, n) : # sorting the array in # descending order a.sort(reverse = True) # store the final sum of # all the rectangles area # possible sum = 0 flag = False # temporary variable to store # the length of rectangle len = 0 i = 0 while (i < n-1) : if(i != 0) : i = i + 1 # Selecting the length of # rectangle so that difference # between any two number is 1 # only. Here length is selected # so flag is set if ((a[i] == a[i + 1] or a[i] - a[i + 1] == 1) and flag == False) : # flag is set means # we have got length of # rectangle flag = True # length is set to # a[i+1] so that if # a[i+1] is less than a[i] # by 1 then also we have # the correct choice for length len = a[i + 1] # incrementing the counter # one time more as we have # considered a[i+1] element # also so. i = i + 1 # Selecting the width of rectangle # so that difference between any # two number is 1 only. Here width # is selected so now flag is again # unset for next rectangle elif ((a[i] == a[i + 1] or a[i] - a[i + 1] == 1) and flag == True) : # area is calculated for # rectangle sum = sum + a[i + 1] * len # flag is set false # for another rectangle # which we can get from # elements in array flag = False # incrementing the counter # one time more as we have # considered a[i+1] element # also so. i = i + 1 return sum # Driver code a = [ 10, 10, 10, 10, 11, 10, 11, 10, 9, 9, 8, 8 ] n = len(a) print (MaxTotalRectangleArea(a, n)) # This code is contributed by # Manish Shaw (manishshaw1)
C#
// C# code to find sum of all area rectangle
// possible
using System;
class GFG {
// Function to find
// area of rectangles
static int MaxTotalRectangleArea(int []a,
int n)
{
// sorting the array in descending
// order
Array.Sort(a);
Array.Reverse(a);
// store the final sum of all the
// rectangles area possible
int sum = 0;
bool flag = false;
// temporary variable to store the
// length of rectangle
int len =0;
for (int i = 0; i < n; i++)
{
// Selecting the length of
// rectangle so that difference
// between any two number is 1
// only. Here length is selected
// so flag is set
if ((a[i] == a[i + 1] || a[i] -
a[i + 1] == 1) && (!flag))
{
// flag is set means
// we have got length of
// rectangle
flag = true;
// length is set to
// a[i+1] so that if
// a[i] a[i+1] is less
// than by 1 then also
// we have the correct
// choice for length
len = a[i + 1];
// incrementing the counter
// one time more as we have
// considered a[i+1] element
// also so.
i++;
}
// Selecting the width of rectangle
// so that difference between any
// two number is 1 only. Here width
// is selected so now flag is again
// unset for next rectangle
else if ((a[i] == a[i + 1] ||
a[i] - a[i + 1] == 1) && (flag))
{
// area is calculated for
// rectangle
sum = sum + a[i + 1] * len;
// flag is set false
// for another rectangle
// which we can get from
// elements in array
flag = false;
// incrementing the counter
// one time more as we have
// considered a[i+1] element
// also so.
i++;
}
}
return sum;
}
// Driver code
static public void Main ()
{
int []a = { 10, 10, 10, 10,
11, 10, 11, 10,
9, 9, 8, 8 };
int n = a.Length;
Console.WriteLine(
MaxTotalRectangleArea(a, n));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP code to find sum
// of all area rectangle
// possible
// Function to find
// area of rectangles
function MaxTotalRectangleArea( $a, $n)
{
// sorting the array in
// descending order
rsort($a);
// store the final sum of
// all the rectangles area
// possible
$sum = 0;
$flag = false;
// temporary variable to store
// the length of rectangle
$len;
for ( $i = 0; $i < $n; $i++)
{
// Selecting the length of
// rectangle so that difference
// between any two number is 1
// only. Here length is selected
// so flag is set
if (($a[$i] == $a[$i + 1] or $a[$i] -
$a[$i + 1] == 1) and (!$flag))
{
// flag is set means
// we have got length of
// rectangle
$flag = true;
// length is set to
// a[i+1] so that if
// a[i+1] is less than a[i]
// by 1 then also we have
// the correct choice for length
$len = $a[$i + 1];
// incrementing the counter
// one time more as we have
// considered a[i+1] element
// also so.
$i++;
}
// Selecting the width of rectangle
// so that difference between any
// two number is 1 only. Here width
// is selected so now flag is again
// unset for next rectangle
else if (($a[$i] == $a[$i + 1] or
$a[$i] - $a[$i + 1] == 1) and
($flag))
{
// area is calculated for
// rectangle
$sum = $sum + $a[$i + 1] * $len;
// flag is set false
// for another rectangle
// which we can get from
// elements in array
$flag = false;
// incrementing the counter
// one time more as we have
// considered a[i+1] element
// also so.
$i++;
}
}
return $sum;
}
// Driver code
$a = array( 10, 10, 10, 10,
11, 10, 11, 10,
9, 9, 8, 8 );
$n = count($a);
echo MaxTotalRectangleArea($a, $n);
//This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript code to find sum of all
// area rectangle possible
// Function to find
// area of rectangles
function MaxTotalRectangleArea( a, n)
{
// sorting the array in
// descending order
a.sort();
a.reverse();
// store the final sum of
// all the rectangles area
// possible
let sum = 0;
let flag = false;
// temporary variable to store
// the length of rectangle
let len;
for (let i = 0; i < n; i++)
{
// Selecting the length of
// rectangle so that difference
// between any two number is 1
// only. Here length is selected
// so flag is set
if ((a[i] == a[i + 1] || a[i] -
a[i + 1] == 1) && (!flag))
{
// flag is set means
// we have got length of
// rectangle
flag = true;
// length is set to
// a[i+1] so that if
// a[i] a[i+1] is less
// than by 1 then also
// we have the correct
// choice for length
len = a[i + 1];
// incrementing the counter
// one time more as we have
// considered a[i+1] element
// also so.
i++;
}
// Selecting the width of rectangle
// so that difference between any
// two number is 1 only. Here width
// is selected so now flag is again
// unset for next rectangle
else if ((a[i] == a[i + 1] ||
a[i] - a[i + 1] == 1) && (flag))
{
// area is calculated for
// rectangle
sum = sum + a[i + 1] * len;
// flag is set false
// for another rectangle
// which we can get from
// elements in array
flag = false;
// incrementing the counter
// one time more as we have
// considered a[i+1] element
// also so.
i++;
}
}
return sum;
}
// Driver Code
let a = [ 10, 10, 10, 10,
11, 10, 11, 10,
9, 9, 8, 8 ];
let n = a.length;
document.write(MaxTotalRectangleArea(a, n));
</script>
Producción
282
Complejidad de tiempo: O(nlog(n))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Surya Priy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA