Largest rectangle
(Mylib/Typical/max_rectangle.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• max_rectangle_in_histogram(T h[H][W])
  • Time complexity $O(HW)$

Requirements

Notes

Problems

• AOJ DPL_3_B Largest Rectangle
• ARC 081 F - Flip and Rectangles ((w+1)(h+1)の最大値を求める変種)

References

Depends on

• Largest rectangle in histogram (Mylib/Typical/max_rectangle_in_histogram.cpp)

Verified with

• test/aoj/DPL_3_B/main.test.cpp

Code

#pragma once
#include <algorithm>
#include <vector>
#include "Mylib/Typical/max_rectangle_in_histogram.cpp"

namespace haar_lib {
  template <typename T>
  int max_rectangle(const std::vector<std::vector<T>> &d, T value) {
    const int H = d.size();
    const int W = d[0].size();

    std::vector<std::vector<int>> c(H, std::vector<int>(W));
    for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        if (d[i][j] == value) c[i][j] = 1;
      }
    }

    for (int i = 1; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        if (c[i][j]) {
          c[i][j] += c[i - 1][j];
        }
      }
    }

    int ret = 0;
    for (int i = 0; i < H; ++i) {
      int t = max_rectangle_in_histogram<int>(c[i]);
      ret   = std::max(ret, t);
    }

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Typical/max_rectangle.cpp"
#include <algorithm>
#include <vector>
#line 2 "Mylib/Typical/max_rectangle_in_histogram.cpp"
#include <stack>
#include <utility>
#line 5 "Mylib/Typical/max_rectangle_in_histogram.cpp"

namespace haar_lib {
  template <typename T>
  T max_rectangle_in_histogram(const std::vector<T> &h) {
    std::stack<std::pair<T, int>> st;
    T ret = 0;

    for (size_t i = 0; i < h.size(); ++i) {
      if (st.empty()) {
        st.emplace(h[i], i);
      } else if (st.top().first < h[i]) {
        st.emplace(h[i], i);
      } else if (st.top().first > h[i]) {
        int j = i;
        while (not st.empty() and st.top().first > h[i]) {
          ret = std::max(ret, st.top().first * ((T) i - st.top().second));
          j   = st.top().second;
          st.pop();
        }
        st.emplace(h[i], j);
      }
    }

    while (not st.empty()) {
      ret = std::max(ret, st.top().first * ((T) h.size() - st.top().second));
      st.pop();
    }

    return ret;
  }
}  // namespace haar_lib
#line 5 "Mylib/Typical/max_rectangle.cpp"

namespace haar_lib {
  template <typename T>
  int max_rectangle(const std::vector<std::vector<T>> &d, T value) {
    const int H = d.size();
    const int W = d[0].size();

    std::vector<std::vector<int>> c(H, std::vector<int>(W));
    for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        if (d[i][j] == value) c[i][j] = 1;
      }
    }

    for (int i = 1; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        if (c[i][j]) {
          c[i][j] += c[i - 1][j];
        }
      }
    }

    int ret = 0;
    for (int i = 0; i < H; ++i) {
      int t = max_rectangle_in_histogram<int>(c[i]);
      ret   = std::max(ret, t);
    }

    return ret;
  }
}  // namespace haar_lib

Back to top page