11. Container With Most Water

• https://leetcode.com/problems/container-with-most-water/

O(n²) なアルゴリズムを書いてTLEを食らって、枝刈りするようにしてみたが結局解けず。

• https://github.com/inohiro/LeetCode/blob/master/11_container_with_most_water/self_2.rb

解説を読んだところ、配列の始まりと終わりから範囲を狭めながら、得られる面積の最大値を求める。確かに最大の面積を求めたいのだから、狭い範囲から探すよりも、広い範囲から探すほうが理にかなっているか。2つの添字を動かしながらなんとかする、という問題が続いた。解き方のアイデアさえも思い浮かばないことが多いけど、数をこなせばふわっとわかるようになるんだろうか...

• https://github.com/inohiro/LeetCode/blob/master/11_container_with_most_water/solution.rb

---

• あまり考えずに手を動かしてしまうことが多いので、よく考えてから動くようにしている。結局やろうとしていることを説明できないといけないわけで。
• 久しぶりに HackerRank を見たら、問題の種類から選べる画面があることに気がついて、これはこれで良さそうだ
  • 例えば動的計画法を使う問題の一覧がある https://www.hackerrank.com/domains/algorithms/dynamic-programming