LeetCode / Best Time to Buy and Sell Stock II @柏の葉コワーキングスペースKOIL

今日は柏の葉のコワーキングスペースに来てみました。

www.31ventures.jp

日本最大級らしいので、ここまでのクオリティが他でもあるわけではないと思いますが、
1日(9時-23時まで)で1500円
ということで、圧倒的なコスパに驚愕しております。

柏の葉ということで私の自宅からdoor2doorで1時間弱かかるんですが、移動疲れせず、ここまで来たらやってやろうと言う気持ちになる、ちょうど良い具合の立地です。


さて、今日の問題。

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Example 2:

Example 3:

前回記事の類題です。
今度は1度切りの売り買いではなく、何度も売り買いを繰り返したとき、最大の利益はいくらになるか算出する問題です。
但し同日に売り買いすることはできないとします。

解答・解説

解法1

今回の問題は、次の日に値が上がるか同じなら売らずに待ち、下がるなら売るという最適な行動に気づけば、簡単です。

そして、また簡潔なコードとイマイチなコードを並べておきます。

まずは私のsubmitしたコード。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit, sell, buy = 0, float('-inf'), float('inf')
        i = 0
        while i < len(prices):
            buy = min(buy, prices[i])
            if prices[i] > buy:
                sell = prices[i]
                while i < len(prices)-1 and sell <= prices[i+1]:
                    sell = prices[i+1]
                    i += 1
                max_profit += sell - buy
                sell, buy = float('-inf'), float('inf')
            i += 1
        return max_profit

次の日に値が上がるか同じなら売らずに待ち、下がるなら売るという行動をそのままコードに落としています。

解法2

続いてSolutionをPythonに翻訳したコードです。考え方は上と同じですが、
「値が下がるまで売らずに待つ」ときに得られる利益は、1日ごとの値の差分の和と同値である
という関係性を使って、より簡潔なコードに落としています。
下図のイメージです。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2:
            return 0
        else:
            profit = 0
            for i in range(len(prices)-1):
                if prices[i] < prices[i+1]:
                    profit += prices[i+1] - prices[i]
            return profit