Subarray binaria de rectángulo de tamaño máximo con todos 1 | conjunto 2

Dada una array binaria mat[][] de tamaño N*M , encuentre la subarray binaria de rectángulo de tamaño máximo con todos los 1. 

Ejemplos:

Entrada: mat[][] = { {0, 1, 1, 0}, 
                                {1, 1, 1, 1}, 
                               {1, 1, 1, 1}, 
                              {1, 1, 0, 0} }
Salida : 8
Explicación: El rectángulo más grande formado con solo 1 es: (0, 1) a (2, 2) o (1, 1) a (2, 3) que es
1 1 1 1
1 1 1 1

Entrada: mat[][] = { {0, 1, 1}, 
                                {1, 1, 1}, 
                               {0, 1, 1} }
Salida: 6
Explicación: El rectángulo más grande con solo 1 es de (0, 1 ) a (2, 2) que es
1 1
1 1
1 1

Enfoque: este enfoque utiliza el concepto de área rectangular más grande en histograma . Pero el enfoque para obtener el área máxima para cada fila será diferente al de Set-1 . 

• Considere cada fila como la base del gráfico de histograma formado con todos los 1.
• Para cada fila, aumente la altura de una barra en la cantidad de la fila anterior, solo si el valor en la fila actual es 1 y calcule el área rectangular más grande de ese histograma .
• El área rectangular más grande de un histograma entre todas las filas base posibles es el área requerida del rectángulo.

Ilustración:

Considere la array:
mat[][] = 0 1 1 0
                  1 1 1 1
                  1 1 1 1
                  1 1 0 0 

Calcule maxarea para la primera fila mat[0]
        => altura fila[0] = 0 1 1 0. 
        => área = altura* ancho = 1 * 2 = 2

Calcule el área máxima para la primera fila mat[1]
        => actualice la altura de mat[1] con mat[0], es decir, mat[1][i] = mat[0][i] + 1 si mat[1][i ] = 1, sino 0
        => altura fila[1] = 1 2 2 1. 
        => área = altura* ancho = 2 * 2 = 4

Calcule el área máxima para la primera fila mat[2]
        => actualice la altura de mat[2] con mat[1]. es decir, mat[2][i] = mat[1][i] + 1 si mat[2][i] = 1, sino 0.
        => altura fila[2] = 2 3 3 2. 
        => área = alto* ancho = 2 * 4 = 8 (el siguiente índice más pequeño de mat[2][0] = 4, y el anterior índice más pequeño = 0. área = 2*(4 – 0))

Calcule el área máxima para la primera fila mat[3]
        => actualice la altura de mat[3] con mat[2]. es decir, mat[3][i] = mat[2][i] + 1 si mat[3][i] = 1, sino 0.
        => altura fila[3] = 3 4 0 0. 
        => área = altura* ancho = 3 * 2 = 6 (el siguiente índice más pequeño de mat[3][0] = 2, y el índice más pequeño anterior = 0. area = 3*(2 – 0))
        => aquí 3 4 0 0 se debe a la razón por la que cuando mat[i][j] = 0 no se agregan alturas anteriores. 

Por lo tanto maxarea = max of(2, 4, 8, 6) = 8.

Este enfoque se puede dividir en dos partes: 

• Calcule las alturas del histograma para cada fila como base. 
  • Ejecute un bucle para atravesar las filas.
  • Ahora, si la fila actual no es la primera fila, actualice la altura de esa celda de la siguiente manera,  
    • Si mat[i][j] no es cero, entonces matrix[i][j] = matrix[i-1][j] + matrix[i][j] . 
    • De lo contrario mat[i][j] = 0 .
• Calcule el área rectangular más grande en el histograma de 1 para cada fila como base.
  • Primero calcule las alturas para cada fila como base como se mencionó anteriormente.
  • Cree dos arrays nextSmallereElemen[] y anteriorSmallerElement[] para almacenar los índices de los elementos anteriores más pequeños y los siguientes elementos más pequeños, respectivamente. Consulte este artículo para encontrar el elemento más pequeño anterior y siguiente .
  • Ahora, para cada elemento, calcule el área tomando este j-ésimo elemento como el más pequeño en el rango nextSmallereElemen[j] y anteriorSmallerElement[j] y multiplicándolo por la diferencia de nextSmallereElemen[j]  y anteriorSmallerElement[j] . 
    • Entonces, la altura será el j-ésimo elemento en la array de entrada dada. Y el ancho será, ancho = nextSmallereElemen[j] – anteriorSmallerElement[j] .
  • Finalmente, encuentre el máximo de todas las áreas para obtener el área máxima deseada.
• Encuentre las áreas máximas entre todas las filas, y esa será el área requerida del rectángulo.

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

// C++ code for the above approach:
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find next smaller element
vector<int> nextsmallerelement(vector<int>& arr,
                               int n)
{
 
    stack<int> st;
 
    // For the elements which dont have
    // next smaller element ans will be -1
    st.push(-1);
 
    // Store indices in output
    vector<int> right(n);
 
    // Start from last index
    for (int i = n - 1; i >= 0; i--) {
 
        // If top element is sorted then
        // no need to do anything, just store
        // the answer and push the
        // current element in stack
        if ((st.top() != -1)
            && arr[st.top()] < arr[i]) {
            right[i] = st.top();
            st.push(i);
        }
        else {
            while ((st.top() != -1)
                   && arr[st.top()]
                          >= arr[i]) {
                st.pop();
            }
            right[i] = st.top();
            st.push(i);
        }
    }
    return right;
}
 
// Function to find previous smaller element
vector<int> previousmallerelement(vector<int>& arr,
                                  int n)
{
    stack<int> st;
    st.push(-1);
    vector<int> left(n);
 
    // Start from first index
    for (int i = 0; i < n; i++) {
        if ((st.top() != -1)
            && arr[st.top()] < arr[i]) {
            left[i] = st.top();
            st.push(i);
        }
        else {
            while ((st.top() != -1)
                   && arr[st.top()]
                          >= arr[i]) {
                st.pop();
            }
            left[i] = st.top();
            st.push(i);
        }
    }
    return left;
}
 
// Function to get the maximum area
// considering each row as the histogram base
int getMaxArea(vector<int>& arr, int n)
{
    vector<int> right(n);
    right = nextsmallerelement(arr, n);
 
    // Find the smallest element than
    // curr element in right side
 
    vector<int> left(n);
    left = previousmallerelement(arr, n);
 
    // Find the smallest element
    // than curr element in left side
    int maxarea = INT_MIN;
 
    // Now the left and right vector have
    // index of smallest element in left and
    // right respectively, thus the difference
    // of right - left - 1 will give us
    // breadth and thus
    // area = height(curr==arr[i]) * breadth;
    for (int i = 0; i < n; i++) {
        int height = arr[i];
        if (right[i] == -1) {
            right[i] = n;
        }
        int breadth = right[i] - left[i] - 1;
        maxarea = max(maxarea,
                      height * breadth);
    }
    return maxarea;
}
 
// Function to calculate
// the maximum area of rectangle
int maxRectangleArea(vector<vector<int> >& M,
                     int n, int m)
{
 
    // Calculate maxarea for first row
    int area = getMaxArea(M[0], m);
    int maxarea = area;
 
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (M[i][j] != 0) {
 
                // Add heights of previous rows
                // into current
                M[i][j] = M[i][j]
                          + M[i - 1][j];
            }
            else {
 
                // If current height is 0 then
                // don't add previous heights
                M[i][j] = 0;
            }
        }
        maxarea = max(maxarea,
                      getMaxArea(M[i], m));
    }
    return maxarea;
}
 
// Driver code
int main()
{
    int N = 4, M = 4;
    vector<vector<int> > amt = {
        { 0, 1, 1, 0 },
        { 1, 1, 1, 1 },
        { 1, 1, 1, 1 },
        { 1, 1, 0, 0 },
    };
 
    cout << maxRectangleArea(amt, N, M);
    return 0;
}

/*package whatever //do not write package name here */
import java.util.*;
class GFG{
 
  public static int[] nextsmallerelement(int[] arr, int n)
  {
 
    Stack<Integer> st = new Stack<>();
 
    // For the elements which dont have
    // next smaller element ans will be -1
    st.push(-1);
 
    // Store indices in output
    int[] right  = new int[n];
 
    // Start from last index
    for (int i = n - 1; i >= 0; i--) {
 
      // If top element is sorted then
      // no need to do anything, just store
      // the answer and push the
      // current element in stack
      if ((st.peek() != -1)
          && arr[st.peek()] < arr[i]) {
        right[i] = st.peek();
        st.push(i);
      }
      else {
        while ((st.peek() != -1)
               && arr[st.peek()]
               >= arr[i]) {
          st.pop();
        }
        right[i] = st.peek();
        st.push(i);
      }
    }
    return right;
  }
 
  public static int[] previousmallerelement(int arr[],int n)
  {
    Stack<Integer> st = new Stack<>();
    st.push(-1);
 
    int[] left  = new int[n];
 
    // Start from first index - Difference Between Next and Previous Smaller element
    for (int i = 0; i < n; i++) {
      if ((st.peek() != -1)
          && arr[st.peek()] < arr[i]) {
        left[i] = st.peek();
        st.push(i);
      }
      else {
        while ((st.peek() != -1)
               && arr[st.peek()]
               >= arr[i]) {
          st.pop();
        }
        left[i] = st.peek();
        st.push(i);
      }
    }
    return left;
  }
 
  public static int getMaxArea(int [] arr, int n)
  {
    int [] right = new int [n];
    right = nextsmallerelement(arr, n);
 
    // Find the smallest element than
    // curr element in right side
 
    int [] left = new int [n];
    left = previousmallerelement(arr, n);
 
    // Find the smallest element
    // than curr element in left side
    int maxarea = Integer.MIN_VALUE;
 
    // Now the left and right array have
    // index of smallest element in left and
    // right respectively, thus the difference
    // of right - left - 1 will give us
    // breadth and thus
    // area = height(curr==arr[i]) * breadth;
    for (int i = 0; i < n; i++) {
      int height = arr[i];
      if (right[i] == -1) {
        right[i] = n;
      }
      int breadth = right[i] - left[i] - 1;
      maxarea = Math.max(maxarea,
                         height * breadth);
    }
    return maxarea;
  }
 
  public static int maxRectangleArea(int [][] M, int R, int C)
  {
    int area = getMaxArea(M[0], R);
    int maxarea = area;
 
    for (int i = 1; i < R; i++) {
      for (int j = 0; j < C; j++) {
        if (M[i][j] != 0) {
 
          // Add heights of previous rows
          // into current
          M[i][j] = M[i][j]
            + M[i - 1][j];
        }
        else {
 
          // If current height is 0 then
          // don't add previous heights
          M[i][j] = 0;
        }
      }
      maxarea = Math.max(maxarea,
                         getMaxArea(M[i], R));
    }
    return maxarea;
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    // Given array
    int R = 4, C = 4;
    int [][]amt = {
      { 0, 1, 1, 0 },
      { 1, 1, 1, 1 },
      { 1, 1, 1, 1 },
      { 1, 1, 0, 0 },
    };
    System.out.println(maxRectangleArea(amt, R, C));
  }
}
 
// This code is contributed by rupeshsk30.

# Python code for the above approach:
 
INT_MIN = -2147483647 - 1
 
# Function to find next smaller element
def nextsmallerelement(arr, n):
 
    st = []
 
    # For the elements which dont have
    # next smaller element ans will be -1
    st.append(-1)
 
    # Store indices in output
    right = [0 for i in range(n)]
 
    # Start from last index
    for i in range(n-1,-1,-1):
 
# If top element is sorted then
# no need to do anything, just store
# the answer and append the
# current element in stack
        if ((st[- 1] != -1) and arr[st[- 1]] < arr[i]):
            right[i] = st[- 1]
            st.append(i)
        else:
            while ((st[- 1] != -1) and arr[st[- 1]] >= arr[i]):
                st.pop()
     
            right[i] = st[- 1]
            st.append(i)
    return right
 
# Function to find previous smaller element
def previousmallerelement(arr, n):
    st = []
    st.append(-1)
    left = [0 for i in range(n)]
 
    # Start from first index
    for i in range(n):
        if((st[- 1] != -1) and arr[st[- 1]] < arr[i]):
            left[i] = st[- 1]
            st.append(i)
        else:
            while ((st[- 1] != -1) and arr[st[- 1]]>= arr[i]):
                st.pop()
             
            left[i] = st[- 1]
            st.append(i)
 
    return left
 
# Function to get the maximum area
# considering each row as the histogram base
def getMaxArea(arr, n):
    right = [0 for i in range(n)]
    right = nextsmallerelement(arr, n)
 
    # Find the smallest element than
    # curr element in right side
 
    left = [0 for i in range(n)]
    left = previousmallerelement(arr, n)
 
    # Find the smallest element
    # than curr element in left side
    maxarea = INT_MIN
 
    # Now the left and right vector have
    # index of smallest element in left and
    # right respectively, thus the difference
    # of right - left - 1 will give us
    # breadth and thus
    # area = height(curr==arr[i]) * breadth
    for i in range(n):
        height = arr[i]
        if (right[i] == -1):
            right[i] = n
 
        breadth = right[i] - left[i] - 1
        maxarea = max(maxarea,height * breadth)
     
    return maxarea
 
# Function to calculate
# the maximum area of rectangle
def maxRectangleArea(M, n, m):
 
    # Calculate maxarea for first row
    area = getMaxArea(M[0], m)
    maxarea = area
 
    for i in range(1,n):
        for j in range(m):
            if (M[i][j] != 0):
 
                # Add heights of previous rows into current
                M[i][j] = M[i][j] + M[i - 1][j]
 
            else:
 
                # If current height is 0 then
                # don't add previous heights
                M[i][j] = 0
 
        maxarea = max(maxarea,getMaxArea(M[i], m))
    return maxarea
 
# Driver code
 
N,M = 4,4
amt = [ [0, 1, 1, 0],[1, 1, 1, 1],[1, 1, 1, 1],[1, 1, 0, 0]]
 
print(maxRectangleArea(amt, N, M))
 
# This code is contributed by shinjanpatra

<script>
    // JavaScript code for the above approach:
 
    const INT_MIN = -2147483647 - 1;
 
    // Function to find next smaller element
    const nextsmallerelement = (arr, n) => {
 
        let st = [];
 
        // For the elements which dont have
        // next smaller element ans will be -1
        st.push(-1);
 
        // Store indices in output
        let right = new Array(n).fill(0);
 
        // Start from last index
        for (let i = n - 1; i >= 0; i--) {
 
            // If top element is sorted then
            // no need to do anything, just store
            // the answer and push the
            // current element in stack
            if ((st[st.length - 1] != -1)
                && arr[st[st.length - 1]] < arr[i]) {
                right[i] = st[st.length - 1];
                st.push(i);
            }
            else {
                while ((st[st.length - 1] != -1)
                    && arr[st[st.length - 1]]
                    >= arr[i]) {
                    st.pop();
                }
                right[i] = st[st.length - 1];
                st.push(i);
            }
        }
        return right;
    }
 
    // Function to find previous smaller element
    const previousmallerelement = (arr, n) => {
        let st = [];
        st.push(-1);
        let left = new Array(n).fill(0);
 
        // Start from first index
        for (let i = 0; i < n; i++) {
            if ((st[st.length - 1] != -1)
                && arr[st[st.length - 1]] < arr[i]) {
                left[i] = st[st.length - 1];
                st.push(i);
            }
            else {
                while ((st[st.length - 1] != -1)
                    && arr[st[st.length - 1]]
                    >= arr[i]) {
                    st.pop();
                }
                left[i] = st[st.length - 1];
                st.push(i);
            }
        }
        return left;
    }
 
    // Function to get the maximum area
    // considering each row as the histogram base
    const getMaxArea = (arr, n) => {
        let right = new Array(n).fill(0);
        right = nextsmallerelement(arr, n);
 
        // Find the smallest element than
        // curr element in right side
 
        let left = new Array(n).fill(0);
        left = previousmallerelement(arr, n);
 
        // Find the smallest element
        // than curr element in left side
        let maxarea = INT_MIN;
 
        // Now the left and right vector have
        // index of smallest element in left and
        // right respectively, thus the difference
        // of right - left - 1 will give us
        // breadth and thus
        // area = height(curr==arr[i]) * breadth;
        for (let i = 0; i < n; i++) {
            let height = arr[i];
            if (right[i] == -1) {
                right[i] = n;
            }
            let breadth = right[i] - left[i] - 1;
            maxarea = Math.max(maxarea,
                height * breadth);
        }
        return maxarea;
    }
 
    // Function to calculate
    // the maximum area of rectangle
    const maxRectangleArea = (M, n, m) => {
 
        // Calculate maxarea for first row
        let area = getMaxArea(M[0], m);
        let maxarea = area;
 
        for (let i = 1; i < n; i++) {
            for (let j = 0; j < m; j++) {
                if (M[i][j] != 0) {
 
                    // Add heights of previous rows
                    // into current
                    M[i][j] = M[i][j]
                        + M[i - 1][j];
                }
                else {
 
                    // If current height is 0 then
                    // don't add previous heights
                    M[i][j] = 0;
                }
            }
            maxarea = Math.max(maxarea,
                getMaxArea(M[i], m));
        }
        return maxarea;
    }
 
    // Driver code
 
    let N = 4, M = 4;
    let amt = [
        [0, 1, 1, 0],
        [1, 1, 1, 1],
        [1, 1, 1, 1],
        [1, 1, 0, 0],
    ];
 
    document.write(maxRectangleArea(amt, N, M));
 
// This code is contributed by rakeshsahni
 
</script>

8

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

Este artículo es una contribución de Rupesh Kapse .