動的計画法/ヒストグラム中の最大長方形
(test/dynamic_programming/largest_rectangle.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_C

Depends on

• ヒストグラム中の最大長方形 (largest rectangle in a histogram) (include/emthrm/dynamic_programming/largest_rectangle.hpp)

Code

/*
 * @title 動的計画法/ヒストグラム中の最大長方形
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_C
 */

#include <iostream>
#include <vector>

#include "emthrm/dynamic_programming/largest_rectangle.hpp"

int main() {
  int n;
  std::cin >> n;
  std::vector<int> h(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> h[i];
  }
  std::cout << emthrm::largest_rectangle(h) << '\n';
  return 0;
}

#line 1 "test/dynamic_programming/largest_rectangle.test.cpp"
/*
 * @title 動的計画法/ヒストグラム中の最大長方形
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_C
 */

#include <iostream>
#include <vector>

#line 1 "include/emthrm/dynamic_programming/largest_rectangle.hpp"



#include <algorithm>
#include <stack>
#line 7 "include/emthrm/dynamic_programming/largest_rectangle.hpp"

namespace emthrm {

template <typename T>
long long largest_rectangle(const std::vector<T>& height) {
  const int n = height.size();
  std::vector<int> left(n);
  std::stack<T> st;
  long long res = 0;
  for (int i = 0; i < n; ++i) {
    while (!st.empty() && height[st.top()] >= height[i]) {
      res = std::max(
          res, static_cast<long long>(height[st.top()]) * (i - left[st.top()]));
      st.pop();
    }
    left[i] = (st.empty() ? 0 : st.top() + 1);
    st.emplace(i);
  }
  while (!st.empty()) {
    res = std::max(
        res, static_cast<long long>(height[st.top()]) * (n - left[st.top()]));
    st.pop();
  }
  return res;
}

}  // namespace emthrm


#line 11 "test/dynamic_programming/largest_rectangle.test.cpp"

int main() {
  int n;
  std::cin >> n;
  std::vector<int> h(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> h[i];
  }
  std::cout << emthrm::largest_rectangle(h) << '\n';
  return 0;
}

Back to top page