competitive/combinatorial_optimization/
largest_pattern.rs

1pub fn largest_square(h: usize, w: usize, ok: impl Fn(usize, usize) -> bool) -> usize {
2    let mut dp = vec![vec![0usize; w + 1]; h + 1];
3    for i in 0..h {
4        for j in 0..w {
5            if ok(i, j) {
6                dp[i + 1][j + 1] = dp[i][j].min(dp[i + 1][j]).min(dp[i][j + 1]) + 1;
7            }
8        }
9    }
10    dp.into_iter()
11        .map(|d| d.into_iter().max().unwrap_or_default())
12        .max()
13        .unwrap_or_default()
14        .pow(2)
15}
16
17pub fn largest_rectangle(hist: &[usize]) -> usize {
18    let mut stack = Vec::<(_, _)>::new();
19    let mut res = 0;
20    for (i, h) in hist.iter().cloned().enumerate() {
21        let mut j = i;
22        while let Some((k, p)) = stack.pop_if(|x| x.1 > h) {
23            res = res.max((i - k) * p);
24            j = k;
25        }
26        if stack.last().is_none_or(|x| x.1 < h) {
27            stack.push((j, h));
28        }
29    }
30    while let Some((i, h)) = stack.pop() {
31        res = res.max((hist.len() - i) * h);
32    }
33    res
34}
35
36pub fn largest_rectangle_in_grid(h: usize, w: usize, ok: impl Fn(usize, usize) -> bool) -> usize {
37    let mut hist = vec![0; w];
38    let mut res = 0;
39    for i in 0..h {
40        for (j, hist) in hist.iter_mut().enumerate() {
41            *hist = if ok(i, j) { *hist + 1 } else { 0 };
42        }
43        res = res.max(largest_rectangle(&hist));
44    }
45    res
46}