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 stack.last().is_some_and(|x| x.1 > h) {
23            let (k, p) = stack.pop().unwrap();
24            res = res.max((i - k) * p);
25            j = k;
26        }
27        if stack.last().map_or(true, |x| x.1 < h) {
28            stack.push((j, h));
29        }
30    }
31    while let Some((i, h)) = stack.pop() {
32        res = res.max((hist.len() - i) * h);
33    }
34    res
35}
36
37pub fn largest_rectangle_in_grid(h: usize, w: usize, ok: impl Fn(usize, usize) -> bool) -> usize {
38    let mut hist = vec![0; w];
39    let mut res = 0;
40    for i in 0..h {
41        for (j, hist) in hist.iter_mut().enumerate() {
42            *hist = if ok(i, j) { *hist + 1 } else { 0 };
43        }
44        res = res.max(largest_rectangle(&hist));
45    }
46    res
47}