I tried LeetCode every day 121 Best Time to Buy and Sell Stock (Python, Go)

What is Leetcode

leetcode.com This is the practice of coding interviews for software developers. A total of more than 1,500 coding questions have been posted, and it seems that the same questions are often asked in actual interviews.

Introduction to golang + algorithm I will solve it with go and Python to strengthen the brain. (Python is weak but experienced)

30th question (problem 121)

121 Best Time to Buy and Sell Stock

the issue's details

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

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Japanese translation

Suppose you have an array whose * i * th element is the price of a particular stock on the * i * day.

If you are allowed to complete only one transaction at most (that is, buy one and sell one share), design an algorithm to find the maximum profit.

Please note that you cannot sell your shares before you buy them.

Example 1:

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.

Example 2:

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

Way of thinking

  1. Initialize the variable that stores the maximum profit and the minimum value to search the entire array

  2. Use min which turns in a loop and returns the smaller one and max which returns the larger one

  3. The return value is max_profit, which is the maximum profit.

Answer code

def maxProfit(prices):
    max_profit, min_price = 0, float('inf')
    for price in prices:
        min_price = min(min_price, price)
        profit = price - min_price
        max_profit = max(max_profit, profit)
    return max_profit

--I'll write it in Go too!

func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}
	max, lowest := 0, 0
	for i := 1; i < len(prices); i++ {
		if prices[i] < prices[lowest] {
			lowest = i
		} else if cur := prices[i] - prices[lowest]; cur > max {
			max = cur
		}
	}
	return max
}

Recommended Posts

I tried LeetCode every day 121 Best Time to Buy and Sell Stock (Python, Go)
I tried LeetCode every day 122. Best Time to Buy and Sell Stock II (Python, Go)
I tried LeetCode every day 112. Path Sum (Python, Go)
I tried LeetCode every day 20. Valid Parentheses (Python, Go)
I tried LeetCode every day 136. Single Number (Python, Go)
I tried LeetCode every day 118. Pascal's Triangle (Python, Go)
I tried LeetCode every day 125. Valid Palindrome (Python, Go)
I tried LeetCode every day 155. Min Stack (Python, Go)
I tried LeetCode every day 9. Palindrome Number (Python, Go)
I tried LeetCode every day 1. Two Sum (Python, Go)
Let Code Day 19 Starting from Zero "121. Best Time to Buy and Sell Stock"
I tried LeetCode every day 141. Linked List Cycle (Python, Go)
I tried LeetCode every day 110. Balanced Binary Tree (Python, Go)
I tried LeetCode every day 14.Longest Common Prefix (Python, Go)
I tried LeetCode every day 119. Pascal's Triangle II (Python, Go)
I tried LeetCode every day 108. Convert Sorted Array to Binary Search Tree (Python, Go)
I tried LeetCode every day 21. Merge Two Sorted Lists (Python, Go)
I tried LeetCode every day 168. Excel Sheet Column Title (Python, Go)
I tried LeetCode every day 111. Minimum Depth of Binary Tree (Python, Go)
I tried LeetCode every day 26. Remove Duplicates from Sorted Array (Python, Go)
I tried LeetCode every day 160. Intersection of Two Linked Lists (Python, Go)
I tried LeetCode every day 167. Two Sum II --Input array is sorted (Python, Go)
[LIVE] I tried to deliver the sunrise and sunset times nationwide every day
I want to restart CentOS 8 on time every day.
I tried to illustrate the time and time in C language
I tried to display the time and today's weather w
I tried to enumerate the differences between java and python
I tried to make GUI tic-tac-toe with Python and Tkinter
I tried to touch Python (installation)
[Introduction to Python3 Day 1] Programming and Python
I tried to make a regular expression of "time" using Python
I tried to display the video playback time (OpenCV: Python version)
I tried to make a periodical process with Selenium and Python
I tried Grumpy (Go running Python).
I tried to easily detect facial landmarks with python and dlib
How to write offline real time I tried to solve E11 with python
I tried to verify and analyze the acceleration of Python by Cython
[Markov chain] I tried to read quotes and negative emotions into Python.
I tried to create a sample to access Salesforce using Python and Bottle
How to write offline real time I tried to solve E12 with python
I tried to summarize Python exception handling
I tried to implement PLSA in Python
I tried to implement permutation in Python
I tried to implement PLSA in Python 2
Python3 standard input I tried to summarize
I tried to implement ADALINE in Python
zipline Function to buy and sell stocks
I tried to implement PPO in Python
[Python] I tried to calculate TF-IDF steadily
I tried to touch Python (basic syntax)
I tried my best to return to Lasso
I tried to make a periodical process with CentOS7, Selenium, Python and Chrome
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 5/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part7 / 22]
I tried to automate internal operations with Docker, Python and Twitter API + bonus
Python programming: I tried to get (crawling) news articles using Selenium and BeautifulSoup4.
[ES Lab] I tried to develop a WEB application with Python and Flask ②
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 4/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part3 / 22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 1/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 6/22]