LeetCode. Best Time to Buy and Sell Stock [Dynamic Programming]

Problem:

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.

 

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.

 

-Summary-

Idea: Keep update the minimum value and find maximum profit (high peak) by comparison.

1. Set the minimum price as the highest number before the loop and maximum price number as 0.

2. - Inside the loop, if index i of the list have less value then-current minimum price, we update

   - Otherwise, we compare the current max profit we have and max profit we can get from the current index.

3. return maximum profit

-Similar Solution-

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = sys.maxsize
        max_profit = 0
        
        for price in prices:
            min_price = min(min_price, price)
            max_profit = max(max_profit, price - min_price)
            
        return max_profit

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]