【LeetCode】Best Time to Buy and Sell Stock 解法

LeetCode - Best Time to Buy and Sell Stock

leetcode.com

自分的な解法はfinalである。 v1は5800ms、finalは120ms。 v1はスライス多様しすぎなへっぽこコード。 finalはsolutionに書かれていたものを理解したもの。

ループを時系列に例えて、その際の最小値と最大利益を順次計算している。

ちなみにmaxProfitはsolution内の書き込みだが、よく理解していない。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        if len(prices) <= 1:
            return 0

        d = [prices[i]-prices[i-1] for i in range(1,len(prices))]

        g = [0]*len(d)
        g[0] = d[0]

        for i in range(1,len(d)):
            g[i] = max(d[i], g[i-1] + d[i])

        return max(0,max(g))

        
    def final(self, prices):
        minprice = 9999999999 # sys.maxsize
        maxprofit = 0
        for price in prices:
            if price < minprice:
                minprice = price
            elif price - minprice > maxprofit:
                maxprofit = price - minprice
        
        return maxprofit
        
        
    def v1(self, prices):
        
        max_ = 0
        
        for i in range(0,len(prices)-1):
            v = prices[i]
            p = max(prices[i+1:]) - v
            #max_ = max([max_, p])
            max_ = max_ if max_ > p else p
            
        return max_