[PYTHON] Let Code Day 19 Starting from Zero "121. Best Time to Buy and Sell Stock"

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day18 starting from zero "53. Maximum Subarray"

Basically, I would like to solve the easy acceptance in descending order.

problem

121. Best Time to Buy and Sell Stock

If you've ever played a competition pro, you've probably seen a similar problem. Algorithm and data structure for programming contest capture Especially in this book.

You will be given an array containing the stock prices for each date. Since transactions are allowed only once, the problem is to design an algorithm that maximizes profits. You cannot sell it before you buy it.

Input: [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price.

You can get the maximum profit by buying when the stock price is 1 and selling when the stock price is 6. And it returns 5 which is the profit at that time.

Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.

In this case, 0 is returned because there is no profitable combination.

solution

As an easy-to-understand thing, when I saw the problem, I wondered if there was a way to lick a given sequence from the front, compare the minimum value with the maximum value, and update it.

Let's try it anyway.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        mx, mn = 0, prices and prices[0]
        for i in range(1,len(prices)):
            if prices[i] > prices[i-1]:
                mx = max(mx,prices[i]-mn)
            else:
                mn = min(mn,prices[i])
        return mx
# Runtime: 68 ms, faster than 43.79% of Python3 online submissions for Best Time to Buy and Sell Stock.
# Memory Usage: 15.2 MB, less than 5.75% of Python3 online submissions for Best Time to Buy and Sell Stock.

I don't think it's a good answer because it seems like the idea that it should be solved ...

I was wondering if there was any good answer and I was looking at the discussion, but it was float (inf) I wondered what it was because there are many answers using, and when I looked it up, it was an object called ʻinf` that represents infinity.

Built-in functions

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        mx, mn = 0, float('inf')
        for price in prices:
            mn = min(mn, price)
            pro = price - mn
            mx = max(mx, pro)
        return mx
# Runtime: 72 ms, faster than 26.68% of Python3 online submissions for Best Time to Buy and Sell Stock.
# Memory Usage: 15.1 MB, less than 5.75% of Python3 online submissions for Best Time to Buy and Sell Stock.

When I rewrite it using float (inf), it looks like this. I don't know much, so watching discuss is a learning experience.

If there is an answer that looks good, I will add it.