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

Problem

Best Time to Buy and Sell Stock

Solution

Description

• 특정 주식을 구매할 하루 + 특정 주식을 판매할 미래의 하루를 합친 최대 이익 구하기
• 단, 이익을 얻을 수 없으면 0 반환.

Hint

이 문제는 헷갈릴 수 있지만, “전체 배열에서 가장 싼 날”과 “전체 배열에서 가장 비싼 날” 을 찾으면 안된다.

먼저 구매를 진행한 다음, 판매를 진행하는데, 위와 같이 찾을 경우 가장 싼 날이 가장 비싼 날보다 다음에 있을 경우, 바로 구할 수 없게 되기 때문이다.

• ex. [2, 4, 1]

따라서, 다음과 같이 생각해야 한다.

"각 시점에서 과거 최저가를 기억하면서 현재가와 비교"하는 문제

그리고, 각 시점에서 과거 기준 가장 저렴했던 최솟값과 현재 값을 비교한다는 점에서 DP 를 떠올릴 수 있다.

Solve

1. 먼저, n일 동안 최대 이익을 기록할 배열의 크기를 정의한다.
2. 그리고, 최저값의 기본값은 가장 첫 번째 원소로 정의한다.
3. 배열을 순회하면서, 현재값과 과거의 최저값을 비교한다.
4. 이때, 현재 바로 직전까지의 값과, 현재 가격에서 최저가를 뺀 값을 비교한다.

• 즉, 전날까지의 최대 이익 vs 현재 가 - 최저가를 뺀 최대 이익 을 비교한다.

5. 배열의 가장 마지막 값엔 최대 이익이 담겨 있으므로, 이를 반환한다.

class Solution {
    public int maxProfit(int[] prices) {
        // 1. 각 날짜까지 고려했을 때, 최대 이익을 담을 배열 지정
        int[] dp = new int[prices.length];

        // 2. 최저가 정의
        int min = prices[0];
        // 최고가 정의
        int max = 0;

        // 3. 과거의 최저가와 현재 가격을 비교
        for(int i = 1; i < prices.length; i ++) {
            min = Math.min(min, prices[i]);
            // i번째 전날까지의 값과 현재 가격에서 최저가를 뺀 이익을 비교
            dp[i] = Math.max(dp[i - 1], prices[i] - min);
        }

        // 4. dp 배열의 마지막엔 최대 이익이 담겨있으므로, 반환
        return dp[prices.length - 1];
    }
}