[ Top Interview 150 ] 121. Best Time to Buy and Sell Stock

문제

121. Best Time to Buy and Sell Stock

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.

• Input : i번째 주식 가격을 담은 행렬 prices
• Output : 주식을 한 번 사고 이후 팔았을 때 얻을 수 있는 최대 이익
  • 꼭 하루에 한 번 살 수 있고, 산 이후에 한 번 팔 수 있다.
  • 이익을 낼 수 없다면 0을 반환함

문제 풀이 전략

• 기본 전략 : 최저점에서 사서 최고점에서 판다.
• 주식의 최소 가격 min = prices[0], maxProfit = 0(기본값) 으로 설정
• prices를 순회하면서
  • min보다 가격이 작을 경우, min값을 해당 값으로 할당 (최소값 갱신)
  • maxProfit보다 price[i] - min 이 클 경우, maxProfit에 price[i] - min값을 할당 (최대 이익 갱신)
• maxProfit 반환

1차 풀이

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int min = prices[0];

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
                continue;
            }

            if (prices[i] - min > answer) {
                maxProfit = prices[i] - min;
            }
        }

        return maxProfit;
    }
}

모범 답안

• 풀이 전략은 동일
• Math.max(), Math.min()을 사용하여 코드의 가독성을 증대함

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int min = prices[0];

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

        return maxProfit;
    }
}