Python Algorithm Q12

Q12 Best Time to Buy and Sell Stock

---

Q

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Sample Input

Input: prices = [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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints

• 1 <= prices.length <= 10⁴
• 0 <= prices[i] <= 10⁴

1. My “TRY” == Given “TRY”

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_price = 0
        
        for i in range(len(prices)-1):
            for j in range(i+1, len(prices)):
                max_price = max(max_price, prices[j] - prices[i])

        if max_price < 0:
            return 0

        return max_price

a = Solution()
s = [7, 1, 5, 3, 6, 4]
print(a.maxProfit(s))

#expected : 5

Using brute force cannot be the solution. Obviously, execution time will execeed the time limit(=O(n^2)). So better algo is required.

2. My Solution == Given Solution

def maxProfit(self, prices: List[int]) -> int:
        max_price = 0 #max = -sys.maxsize
        min_val = prices[0] #min sys.maxsize

        for N in prices:
            min_val = min(min_val, N)
            max_price = max(max_price, N-min_val)

        return max_price

This answer focused on using the lowest point. Frankly speaking, I saw the diagram in the book. X-axis is idx of the input and Y-axis is the value. From this, you can think of this solution. Keep reminding min_val, then keep comparing previous max_price with current value - min_val.

**sys.maxsize is from the module “sys”. You can assign the largest value that system supports by using “sys.maxsize”.

Overall Review

Don’t be so complicated. Think simply. Just keep searching the smallest one, then subtract it from current value, lastly compare it with previous max. That’s it.

Also visualization is the key point in solving this kind of problems. You can easily get the answer, only watching the diagram.