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

문제

1차원 배열 prices가 주어졌을 때, prices[i]는 i번째 날의 물건의 가격이다.

어떤 날에 물건을 구입하여 다른 날에 물건을 되판다고 할 때, 최대의 이익을 구하는 문제이다.

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

Best Time to Buy and Sell Stock - LeetCode

 

풀이

 

위 그림과 같이 가격이 각 [7, 1, 5, 3, 6, 4] 으로 주어지는 경우,

day 2에 구입하여 day5에 되팔면 5원의 최대 이익을 얻는다. 

 

해결 방법은,

profit : 최대 이익, min : 최소 가격이라고 한다면

profit = 0, min = day1의 가격으로 값을 대입하고 prices를 순서대로 확인한다.

물건을 되팔기 전에 물건을 구입하여야 하므로, 되파는 날이 구입하는 날보다 먼저 올 수 없다. 

 

- prices[i] - min이 profit 보다 큰 경우 profit에 그 값을 저장하고, 그 후 prcies[i]가 min(최소 가격) 보다 더 작은 경우 min에 그 값을 저장한다.

- 이를 끝까지 반복하고 나면 최대 이익은 profit에 저장된다.

 

코드

public class leetcode_121 {
    public int maxProfit(int[] prices) {

        int profit = 0; // 최대 이익
        int min = prices[0]; // 최소 가격

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] - min > profit) // prices[i]에 구입하고 min 가격으로 되팔 때가 최대 이익이면
                profit = prices[i] - min;
            if (prices[i] < min) // prices[i]가 min 가격보다 작은 경우
                min = prices[i];
        }

        return profit;

    }
}