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

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

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

문제접근

가장 싸게 사서 가장 비싸게 샀을 때 얻는 이윤을 구하는 문제이다.
다이나믹 프로그래밍을 이용해서 dp배열에 지금까지 중에서 가장 싼 값을 저장하고 현재 날짜의 가격 prices[i]와 그 전날까지 가장 싼 가격 dp[i-1]을 빼서 이윤을 구한 다음 max와 비교한다.
그리고 오늘 가격이 dp[i-1]보다 싸다면 dp[i]를 오늘 가격으로 바꿔주고 아니라면 dp[i-1]을 넣어준다.

Code

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        int[] dp = new int[prices.length]; // i번째 날까지 중 가장 싼 물건의 값 저장
        dp[0] = prices[0];
        for(int i =1; i<prices.length; i++){
            int profit = prices[i] - dp[i-1]; // 지금까지 가장 싼 물건의 값을 저장하고 오늘 팔았을 때 나올수 있는 이윤을 계산
            if(profit > max){
                // 오늘 이윤이 max보다 크다면 max를 저장
                max = profit;
            }
            dp[i] = (dp[i-1] > prices[i]) ? prices[i] : dp[i-1]; // 오늘 가격이 더 작다면 지금까지 중 가장 낮은 가격이므로 dp[i]에 저장
        }
        return max;
    }
}

어려웠던 점 / 배운 점 / 느낀 점

많이 풀어본 DP문제라서 쉽게 접근해서 풀었던 문제이다. 굳굳