Recipiente con más agua

Dados n enteros no negativos  donde cada uno representa un punto en la coordenada  . Las líneas verticales ‘n’ se dibujan de manera que los dos extremos de la línea i estén en  y  . 
Encuentre dos líneas, que junto con el eje x formen un recipiente, tal que el recipiente contenga la mayor cantidad de agua.
El programa debe devolver un número entero que corresponda al área máxima de agua que se puede contener (área máxima en lugar de volumen máximo suena extraño, pero este es el plano 2D con el que estamos trabajando por simplicidad).

Nota: No puede inclinar el contenedor. 

Ejemplos:  

Input: array = [1, 5, 4, 3]
Output: 6
Explanation : 
5 and 3 are distance 2 apart. 
So the size of the base = 2. 
Height of container = min(5, 3) = 3. 
So total area = 3 * 2 = 6

Input: array = [3, 1, 2, 4, 5]
Output: 12
Explanation : 
5 and 3 are distance 4 apart. 
So the size of the base = 4. 
Height of container = min(5, 3) = 3. 
So total area = 4 * 3 = 12

Solución ingenua:  

• Enfoque: la idea es bastante simple e implica verificar cada par de límites o elementos de la array y averiguar el área máxima bajo cualquier par de límites.
• Algoritmo: 
  1. Cree un ciclo anidado, el ciclo externo atraviesa la array desde 0 hasta el final (el índice de este ciclo es i ).
  2. El ciclo interno atraviesa la array desde i + 1 hasta el final (el índice de este ciclo es j ).
  3. Encuentre el agua que puede estar contenida en el recipiente con la altura de los límites como arreglo[i] y arreglo[j], es decir, área = (j – i)* min(arreglo[i],arreglo[j]) , si esta área es mayor que el máximo actual, actualice el máximo actual
  4. Imprime el máximo actual.
• Implementación:

// C++ code for Max
// Water Container
#include <iostream>
using namespace std;
 
int maxArea(int A[], int len)
{
    int area = 0;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            // Calculating the max area
            area = max(area, min(A[j], A[i]) * (j - i));
        }
    }
    return area;
}
 
// Driver code
int main()
{
    int a[] = { 1, 5, 4, 3 };
    int b[] = { 3, 1, 2, 4, 5 };
 
    int len1 = sizeof(a) / sizeof(a[0]);
    cout << maxArea(a, len1);
 
    int len2 = sizeof(b) / sizeof(b[0]);
    cout << endl << maxArea(b, len2);
}

// Java code for Max 
// Water Container
import java.io.*;
 
class GFG{
 
public static int maxArea(int[] a)
{
 
    int Area = 0;
     
    for(int i = 0; i < a.length; i++)
    {
        for(int j = i + 1; j < a.length; j++)
        {
            Area = Math.max(
                Area, Math.min(a[i], a[j]) *
                              (j - i));
        }
    }
    return Area;
}
 
// Driver code
public static void main(String[] args)
{
    int a[] = { 1, 5, 4, 3 };
    int b[] = { 3, 1, 2, 4, 5 };
 
    System.out.println(maxArea(a));
    System.out.println(maxArea(b));
}
}
 
// This code is contributed by mulchandanimanisha5

# Python3 code for Max
# Water Container
def maxArea(A, Len) :
    area = 0
    for i in range(Len) :
        for j in range(i + 1, Len) :
           
            # Calculating the max area
            area = max(area, min(A[j], A[i]) * (j - i))
    return area
 
# Driver code
a = [ 1, 5, 4, 3 ]
b = [ 3, 1, 2, 4, 5 ]
 
len1 = len(a)
print(maxArea(a, len1))
 
len2 = len(b)
print(maxArea(b, len2))
 
# This code is contributed by divyesh072019.

// C# code for Max
// Water Container
using System;
class GFG
{
 
public static int maxArea(int[] a)
{
 
    int Area = 0;
     
    for(int i = 0; i < a.Length; i++)
    {
        for(int j = i + 1; j < a.Length; j++)
        {
            Area = Math.Max(Area, Math.Min(a[i], a[j]) *
                            (j - i));
        }
    }
    return Area;
}
 
// Driver code
public static void Main(String[] args)
{
    int []a = { 1, 5, 4, 3 };
    int []b = { 3, 1, 2, 4, 5 };
 
    Console.WriteLine(maxArea(a));
    Console.Write(maxArea(b));
}
}
 
// This code is contributed by shivanisinghss2110

<script>
    // Javascript code for Max
    // Water Container
     
    function maxArea(A, len)
    {
        let area = 0;
        for (let i = 0; i < len; i++) {
            for (let j = i + 1; j < len; j++) {
                // Calculating the max area
                area = Math.max(area, Math.min(A[j], A[i]) * (j - i));
            }
        }
        return area;
    }
 
      let a = [ 1, 5, 4, 3 ];
    let b = [ 3, 1, 2, 4, 5 ];
  
    let len1 = a.length;
    document.write(maxArea(a, len1) + "</br>");
  
    let len2 = b.length;
    document.write(maxArea(b, len2));
     
    // This code is contributed by mukesh07.
</script>

6
12

Análisis de Complejidad: 

• Complejidad de tiempo: O(n^2). 
  Como se requiere un recorrido anidado de la array, la complejidad del tiempo es O (n ^ 2)
• Complejidad espacial: O(1). 
  Como no se requiere espacio adicional, la complejidad del espacio es constante.

Solución eficiente:  

• Enfoque: Dada una serie de alturas de líneas de límites del contenedor, encuentre el máximo de agua que se puede almacenar en un contenedor. Así que empieza por el primer y último elemento y comprueba la cantidad de agua que se puede contener y almacena ese recipiente. Ahora surge la pregunta de si existen mejores límites o líneas que puedan contener el máximo de agua. Así que hay una manera inteligente de encontrar eso. Inicialmente, hay dos índices, el primero y el último índice apuntan al primer y último elemento (que actúa como límites del contenedor), si el valor del primer índice es menor que el valor del último índice, aumente el primer índice; de ​​lo contrario, disminuya el último índice. Como la disminución del ancho es constante, siguiendo el proceso anterior se puede llegar a la respuesta óptima.
  El siguiente GIF explica el enfoque.

• Algoritmo: 
  1. Mantenga dos índices, primero = 0 y último = n-1 y un valor max_area que almacena el área máxima.
  2. Ejecute un ciclo hasta que el primero sea menor que el último.
  3. Actualice max_area con el máximo de max_area y min(array[first] , array[last])*(last-first)
  4. si el valor en el arreglo[primero] es mayor que el arreglo[último] entonces actualice el último como el último – 1 de lo contrario actualice primero como el primero + 1
  5. Imprime el área máxima.
• Implementación:

// C++ code for Max
// Water Container
#include<iostream>
using namespace std;
 
int maxArea(int A[], int len)
{
    int l = 0;
    int r = len -1;
    int area = 0;
     
    while (l < r)
    {
        // Calculating the max area
        area = max(area, min(A[l],
                        A[r]) * (r - l));
                         
            if (A[l] < A[r])
                l += 1;
                 
            else
                r -= 1;
    }
    return area;
}
 
// Driver code
int main()
{
    int a[] = {1, 5, 4, 3};
    int b[] = {3, 1, 2, 4, 5};
     
    int len1 = sizeof(a) / sizeof(a[0]);
    cout << maxArea(a, len1);
     
    int len2 = sizeof(b) / sizeof(b[0]);
    cout << endl << maxArea(b, len2);
}
 
// This code is contributed by Smitha Dinesh Semwal

// Java code for Max
// Water Container
import java.util.*;
 
class Area{
 
    public static int maxArea(int A[], int len)
    {
        int l = 0;
        int r = len -1;
        int area = 0;
     
        while (l < r)
        {
            // Calculating the max area
            area = Math.max(area,
                        Math.min(A[l], A[r]) * (r - l));
                         
            if (A[l] < A[r])
                l += 1;
                 
            else
                r -= 1;
        }
        return area;
    }
     
    public static void main(String[] args)
    {
        int a[] = {1, 5, 4, 3};
        int b[] = {3, 1, 2, 4, 5};
     
        int len1 = 4;
        System.out.print( maxArea(a, len1)+"\n" );
     
        int len2 = 5;
        System.out.print( maxArea(b, len2) );
    }
}
 
// This code is contributed by rishabh_jain

# Python3 code for Max
# Water Container
def maxArea( A):
    l = 0
    r = len(A) -1
    area = 0
     
    while l < r:
        # Calculating the max area
        area = max(area, min(A[l],
                        A[r]) * (r - l))
     
        if A[l] < A[r]:
            l += 1
        else:
            r -= 1
    return area
 
# Driver code
a = [1, 5, 4, 3]
b = [3, 1, 2, 4, 5]
 
print(maxArea(a))
print(maxArea(b))

// C# code for Max
// Water Container
using System;
 
class Area{
 
    public static int maxArea(int []A, int len)
    {
        int l = 0;
        int r = len -1;
        int area = 0;
     
        while (l < r)
        {
            // Calculating the max area
            area = Math.Max(area,
                        Math.Min(A[l], A[r]) * (r - l));
                         
            if (A[l] < A[r])
                l += 1;
                 
            else
                r -= 1;
        }
        return area;
    }
     
    // Driver code
    public static void Main()
    {
        int []a = {1, 5, 4, 3};
        int []b = {3, 1, 2, 4, 5};
     
        int len1 = 4;
        Console.WriteLine( maxArea(a, len1));
     
        int len2 = 5;
        Console.WriteLine( maxArea(b, len2) );
    }
}
 
// This code is contributed by Vt_M

<?php
// PHP code for Max
// Water Container
function maxArea($A, $len)
{
    $l = 0;
    $r = $len -1;
    $area = 0;
     
    while ($l < $r)
    {
        // Calculating the max area
        $area = max($area, min($A[$l],
                    $A[$r]) * ($r - $l));
                         
            if ($A[$l] < $A[$r])
                $l += 1;
                 
            else
                $r -= 1;
    }
    return $area;
}
 
// Driver code
$a = array(1, 5, 4, 3);
$b = array(3, 1, 2, 4, 5);
 
$len1 = sizeof($a) / sizeof($a[0]);
echo maxArea($a, $len1). "\n";
 
$len2 = sizeof($b) / sizeof($b[0]);
echo maxArea($b, $len2);
     
// This code is contributed by mits
?>

<script>
 
// Javascript code for Max
// Water Container
function maxArea(A, len)
{
    let l = 0;
    let r = len -1;
    let area = 0;
 
    while (l < r)
    {
         
        // Calculating the max area
        area = Math.max(area, Math.min(A[l],
                        A[r]) * (r - l));
         
        if (A[l] < A[r])
            l += 1;
        else
            r -= 1;
    }
    return area;
}
 
// Driver code
let a = [ 1, 5, 4, 3 ];
let b = [ 3, 1, 2, 4, 5 ];
  
let len1 = a.length;
document.write(maxArea(a, len1) + "</br>");
  
let len2 = b.length;
document.write(maxArea(b, len2));
 
// This code is contributed by rameshtravel07
 
</script>

6
12

Análisis de Complejidad: 

• Complejidad temporal: O(n). 
  Como solo se requiere un recorrido de la array, la complejidad del tiempo es O (n).
• Complejidad espacial: O(1). 
  No se requiere espacio adicional, por lo que la complejidad del espacio es constante.

Análisis de la solución: ¿por qué funciona esta solución?

Cada vez, estamos moviendo nuestro puntero i adelante si la altura de la línea en el i-ésimo índice es más pequeña o el puntero j si la altura de la línea en el j-ésimo índice es más pequeña. Esto significa que cualquiera que sea la línea que sea más pequeña, no la volveremos a considerar, porque esta línea podría ser la respuesta solo si la otra línea es más grande que ella y tiene el ancho máximo y se debe notar que este es el momento en que la otra línea es más grande. así como la distancia máxima de separación. Entonces, no considerarlo tiene sentido.

En otras palabras, estamos obligados a emparejar cada línea con la línea que es mayor que ella y a la máxima distancia, es decir 

Por ejemplo -> 8 5 9 1 10 2 6

aquí, si 8 tiene que estar en la respuesta, entonces otra línea que elijamos debería ser 10, ya que es la primera línea desde el final que está a la distancia máxima aparte de 8 y más larga que 8. Por lo tanto, para que 8 esté en la respuesta , otra línea debe ser 10.

Ahora, supongamos i en 8 y j en 10. Compárelo y mueva el puntero i a 5.

Ahora, puede preguntar, está bien, ha movido el puntero i a 5, pero ¿no puede suceder que 5 pueda emparejarse con otras líneas después de 10, ya que hemos descuidado esas líneas al mover el puntero j a 10?

Entonces, para notar que si 5 hubiera estado en la respuesta, cualquier línea después de 10 debe ser >= 5 y si hay alguna línea después de 10 cuya altura es mayor o igual a 5, entonces su contribución seguramente se habría calculado mientras el puntero ‘i’ estaba en 8.

Entonces, para las combinaciones de líneas que estamos descuidando, ya se han solucionado.