OnesOnly

package com.gokul.demo.Success.Stack;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class NeedAllOnes {

    public static void main(String[] args) throws IOException {
        // Initialize BufferedReader to read input from the console
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // Read the first line to get n and m (dimensions of the matrix)
        String[] dimensions = br.readLine().trim().split(" ");
        int n = Integer.parseInt(dimensions[0]);
        int m = Integer.parseInt(dimensions[1]);

        // Create a 2D array to store the binary matrix
        long[][] matrix = new long[n][m];

        // Read the next n lines to get the binary values for each row
        for (int i = 0; i < n; i++) {
            String[] rowValues = br.readLine().trim().split(" ");
            for (int j = 0; j < m; j++) {
                matrix[i][j] = Integer.parseInt(rowValues[j]);
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[j][i] != 0) {
                    if (matrix[j - 1][i] > 0) {
                        matrix[j][i] = matrix[j - 1][i] + 1;
                    }
                }
            }
        }

        long ans = 0;
        for (int i = m - 1; i > 0; i--) {
            ans = Math.max(ans, histogram(matrix[i], n));
        }

        System.out.println(ans);
    }

    public static long histogram(long[] arr, int n) {
        Stack<Long> stk = new Stack<>();
        List<Long> nse = new ArrayList<>(Collections.nCopies(n, (long) n));

        List<Long> pse = new ArrayList<>(Collections.nCopies(n, -1L));
        stk.push(0l);

        for (int i = 1; i < n; i++) {
            while (!stk.empty() && arr[i] < arr[stk.peek().intValue()]) {
                nse.set(stk.peek().intValue(), (long) i);
                stk.pop();
            }
            stk.push((long) i);
        }

        System.out.println(nse);

        stk.clear();

        stk.push((long) n - 1);

        for (int i = n - 2; i >= 0; i--) {
            while (!stk.empty() && arr[i] < arr[stk.peek().intValue()]) {
                pse.set(stk.peek().intValue(), (long) i);
                stk.pop();
            }
            stk.push((long) i);
        }

        System.out.println(pse);

        long maxVal = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            long ns = nse.get(i);
            long ps = pse.get(i);

            maxVal = Math.max(maxVal, arr[i] * (ns - ps - 1));
        }

        System.out.println("MX --> " + maxVal);

        return maxVal;
    }
}