DPL_3_B: Largest Rectangle
Largest Squareよりも思考・実装が星ひとつ以上増えてRectangle
自力でできそうな気がしませんね!
でも一度は自分で考える
アルゴリズムは2次元DPとスタックを使うとのこと
自分のカンは優先度キューではないかって言ってたんだけどハズレ
ヒントの絵はヒストグラムみたいなグラフに長方形をあてはめたものと
2要素タプルのスタック
ヒストグラムとスタックは何か関連ありそげ
当たり前っちゃあ当たり前
さてどうする
いかにもダメそうだけどLargest Squareの作戦が使えるかどうか確認
もちろんそのままではダメ
長方形だからタテとヨコ別に覚えてもまだうまくいきそうにない
なぜかというと最大になるかもしれない長方形の候補が複数あるから
これは扱いにくそう
表に何を覚えておけば解きやすいのか?
わかりません