leetcode121 を解いてみた

解いているときの方針

自分で1回はプロセスを考える。解けなくてもOK。
解けなかったときは、振り返ることが可能な程度まで言語化する。
※考え方おかしくない？というのがあればご指摘くださいまし。

問題紹介

問題は以下URL参照

最初の考え

• 愚直にやったら時間制限に引っかかりそう...
• 他にいい感じの解法が思いつかないからとりあえず実装してみるか。実装するのは軽いし。

　最初の提出.py

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_num = 0

        for i, bf in enumerate(prices):
            for j, af in enumerate(prices[i:], len(prices)-1):
                tmp = af - bf
                if tmp > max_num:
                    max_num = tmp
        return max_num

案の定Time Limit Exceeded...

思考中

• 重複抜いたらいけるんじゃね？
  • 配列の順序が影響する場合には重複削除はNGな気がする。
• 配列長の半分まで見て、前後の配列長を比較したら冗長な計算省けるのでは？
  • 結果的にこれの考え方は近かったが、しっくり実装できず...。

結果

Solutionsを確認しました(´・ω・｀)

• 最適値を取り得る要素をサーチすればOK
  • 最適な値の場合(ex:0)、max_profitの候補を網羅できるはず(常にbuy < sellとなる)。この候補をサーチする。
  • 負数になった時点で最適値の候補からは外れる。
    -　　You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.を前提とした考え方になる。

変に考えずにシンプルに考えないとだね(´・ω・｀)