[알고리즘 연습] 최대 수익 구하기

최대 수익 구하기

• 인덱스별로 주식의 가격이 적혀있는 리스트가 있다.
• 해당 리스트에서 주식을 사고 팔았을 때 얻을 수 있는 최대 수익은 얼마인지 구해라

---

풀이

def maximizeProfit(nums):
    max_profit = 0
    min_price = nums[0]
    for now in nums:
        profit = now - min_price
        if profit > max_profit:
            max_profit = profit
        if min_price > now:
            min_price = now

    return max_profit

def main():
    print(maximizeProfit([1,2,3,4,5,6,7])) # 6
    print(maximizeProfit([7,6,5,4,3,2,1])) # 0
    print(maximizeProfit([1,2,3,4,3,2,1])) # 3
    print(maximizeProfit([2,8,19,37,4,5])) # 35

• 상당히 기초적인 문제이다.
• 이자나 다른 조건이 없기 떄문에 '최대한 싼 가격'에서 '최대한 비싼 가격'까지의 루트를 찾는 것이 중요하다
• 따라서 첫 인덱스부터 체크하면서 현재의 가장 싼 가격보다 더 싼 가격이 있다면 망설일 필요없이 바꿔주면 된다.
• 그렇게 '가장 싼 가격'을 갱신시켜가면서 동시에 각 인덱스의 값과의 차를 구해 그 최대값을 체크해나가면 간단하게 해결된다.