121. Best Time to Buy and Sell Stock - python3

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.

My Answer 1: Wrong Answer

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        
        mn = min(prices, default=0)
        mx = max(prices, default=0)
        
        if mn == mx:
            return 0
        
        mn_idx = 0
        mx_idx = 0
        
        for i in range(0, len(prices)):
            if prices[i] == mn:
                mn_idx = i
            if prices[i] == mx:
                mx_idx = i
                
        if mn_idx <= mx_idx:
            return mx - mn
        
        mx2 = mn
        mn2 = mx
        
        for i in range(mn_idx, len(prices)):
            if mx2 < prices[i]:
                mx2 = prices[i]
                
        for i in range(0, mx_idx):
            if mn2 > prices[i]:
                mn2 = prices[i]
        
        if mx2 - mn > mx - mn2:
            return mx2 - mn
        else:
            return mx - mn2
        

처음 생각한 것:

1) min 값이 max 값보다 앞에 있으면 return max - min

2) 아닐 경우,

• min 뒤에 있는 값들 중 최대값 max2 를 찾아 max2 - min ,
• max 앞에 있는 값들 중 최소값 min2 를 찾아 max - min2

를 구해서 둘이 비교 -> 더 큰 값을 return

문제점: input = [7,2,4,1] 과 같이 양극에 max, min이 있을 경우
=> 중간(2,4)에서의 profit 이라도 구해야하는데 그러지 않음

max min 이 고정되면 안되는 것 같다.. 나무말고 숲을 보자

(왜인진 모르지만 min(), max() arg is an empty sequence 오류가 나서 각 함수마다 default 값을 지정해줌)

두번째 생각한 것:

buy 와 sell 변수 사용하기

일단 prices[0] 부터 무조건 buy 로
-> buy 보다 작은 값이 나오면 buy = prices[i] ...

이렇게 대충 해보면 될 거 같은데 sell 을 어떻게 처리할지 모르겠음 ㅠㅠ

파이썬이 C언어화 되어가는 모습에 눈물이 나고..

머리가 그대로 굳었다.................................☆

Other Answer 1: (Runtime: 60 ms / Memory Usage: 15.1 MB)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        num_days = len(prices)
        output = 0
        min_price = sys.maxsize
        for i in range(num_days):
            if prices[i] < min_price:
                min_price = prices[i]
            output = max(output, prices[i] - min_price)        
        return output

찾아보니 아무 값(prices[i])에서 최소값(min_price)을 뺀 값 中 최대값을 구하면 되는 간단한 문제였다;
이때 최소값 min_price 는 리스트를 순회하며 계속 바뀔수있음

이게 베스트 코드 같다고 생각

My Answer 2: Accepted (Runtime: 64 ms / Memory Usage: 15.1 MB)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        
        buy = prices[0]
        sell = 0
        maxprofit = 0
        
        for i in range(1, len(prices)):
            if buy > prices[i]:
                buy = prices[i]
            else:
                sell = prices[i]
                maxprofit = max(maxprofit, sell - buy)
        
        return maxprofit

Other Answer 1을 기반으로
아까 두번째로 생각했던 buy 와 sell 변수를 이용해본것.

buy 는 최소값의 역할을 한다.
buy 값보다 큰 값이면 계속 팔고 보기 -> 그 profit 들 中 최대값이 maxprofit