[LeetCode] 121. Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

개요

1. i번째 날짜에 대한 주가가 배열로 주어진다.
2. 최대 이익을 찾아라.
   • 매수와 매도는 한번만 이루어진다.
   • 매수일은 항상 매도일보다 앞선다.
   • 이익을 얻을 수 없다면 0을 리턴해라.

문제 해결 아이디어

매도 구간을 찾자

• 매수일과 매도일은 각각 매도 구간 내 최소, 최대인 시점이다.
  
  ➡️ 매수일일때 값보다 더 작은 값이 등장하면, 현재 매도 구간이 끝나고 새로운 매도 구간이 생긴다.
  ➡️ 이때 이전 매도 구간의 이익을 추산할 수 있다.

🧐 최소 주가가 갱신될 때 매도 구간의 이익을 계산하자

의사 코드

1. 주가 배열을 돌며 최소 주가를 찾는다.
   1-1. 최소 주가보다 현재 주가가 작은가?
   1-1-1. 현재 매도 구간의 이익을 계산하자.
   1-1-2. 현재 이익이 최대인지 확인하고, 최대 이익을 기록한다.
   1-1-3. 최소 주가를 갱신한다.
   1-1-4. 최대 주가를 초기화한다.
2. 주가 배열을 돌며 최대 주가를 찾는다.

for(주가:주가 배열){
	if(주가 < 최소 주가){
		현재 이익 = 최대 주가 - 최소 주가
		if(현재 이익 > 최대 이익){ 최대 이익 = 현재 이익 }
        최소 주가 = 현재값
        최대 주가 = 0
    }
    if(주가 > 최대 주가){ 최대 주가 = 주가 }
}
return 최대 이익

결과

전체 코드 github 링크

다른 풀이

public int maxProfit(int[] prices) {
        int min_price = prices[0];
        int maxprof = 0;

        for(int i=0;i<prices.length;i++){
            maxprof = Math.max(maxprof,prices[i]-min_price);
            min_price = Math.min(prices[i],min_price);
        }

        return maxprof;
    }

나는 min_price가 바뀔 때 max_price를 0으로 초기화해야 한다고 생각했는데,
그럴 필요 없이 min을 갱신하면 계속 prices[i]-min_price 연산을 해서 max_profit인지 체크하면 된다.