121. Best Time to Buy and Sell Stock

問題概要

• integerの配列 prices が入力値
• prices[i] - prices[j] ( i < j ) が最も大きい組み合わせを見つければ良い

単純にループを二重にすると Time Limit Exceeded になるので工夫が必要

問題URL：https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

解法

先頭からループしていき、その時点での最小値が現れたら購入し、それ以外のときに売却。
これを繰り返して最大利益を求めれば良い。

func maxProfit(prices []int) int {
    minPrice := prices[0]
    maxProfit := 0

    for i := 1; i < len(prices); i++ {
        if prices[i] < minPrice {
            // 最小値のときに売っても利益にならない(マイナスになる）
            // minを更新して次へ
            minPrice = prices[i]
            continue
        }

        // 利益を求める。利益が最大ならmaxProfitを更新
        if profit := prices[i] - minPrice; maxProfit < profit {
            maxProfit = profit
        }
    }

    if maxProfit > 0 {
        return maxProfit
    }

    return 0
}

感想

私は、もっとややこしい解き方をして、上記の解法はSolutionsで見つけた。

なんでこんな簡単なことを思いつかなかったのかなーと。

紙とペンで問題を解いてみて、「頭の中で考えたこと」をコードで表現できると良いのかも。

いきなりコードを書きながら考えるのは悪手。