[그리디] Leet code 122. Best Time to Buy and Sell Stock II

리트코드 122번
주식 차트를 보고 낼 수 있는 가장 많은 수익 구하기

풀이1 극대값 - 극소값

매번 상승세일 때 마다 이익을 봐야 최대 이익을 구할 수 있다!

• price와 min_price를 매번 비교하면서 더 작은 값을 극소값으로 저장
• price - min_price인 profit의 최대를 찾기위해 계속 갱신을 해주다가 profit이 이전보다 작아지는 순간 (변곡) max_profit은 극대 - 극소 가된다
• 이후로는 다시 초기화를 해줘야하기때문에 min_price도 다시바꾸고 max_profit도 0으로 비운뒤 다시 찾는다
• 마지막에 찾다가 끝나기 때문에 max_profit에 저장된 값을 더해주면서 return 해줘야합니다
  -> 상승하고있었다면 max_profit이 있을 것이고 하락중이없다면 0이어서 더해줘도 상관없음

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = sys.maxsize
        max_profit = 0
        total = 0

        for price in prices:
            min_price = min(price, min_price)
            profit = price - min_price
            max_profit = max(max_profit, profit)

            if max_profit > profit:  # 하락세로 바뀌는 지점 : 이익 저장해주고 초기화
                min_price = price
                total += max_profit
                max_profit = 0


        return total + max_profit

내가 풀었지만 생각보다 복잡하다...

풀이2 바로 이전과의 가격비교

그리디 답게 좀더 쪼개서 그 순간순간 판단할 수는 없을까.. 앞에 풀이는 상승세를 뭉텅이로 생각해서 그 범위를 구하기위해 코드가 복잡해졌지만 사실 그냥 이전값보다 크면 그 차이를 더해주면 똑같다....
쪼갤 수 있는 한 제일 쪼개주는게 좋은 것 같다!

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        total = 0

        for i in range(1,len(prices)):
            if prices[i] > prices[i-1]:
                total += prices[i] - prices[i-1]

        return total

최적화
아래 처럼 차이가 음수가 나오면(손해면) 0을 더해주기 하한을 정해줘서 간단하게 처리해 줄 수도 있다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        total = 0

        for i in range(1,len(prices)):
            total += max(prices[i] - prices[i-1] , 0)

        return total