[알고리즘] 4번째 공통 알고리즘 문제 풀기

[ujkkk]

📝 Description

무엇을?

• 4번째 공통 알고리즘 문제 풀기

❗️Todo

• [x] https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/

ETC

기타사항

[ujkkk]

class Solution {
    public static int maxProfit(int[] prices, int fee) {

        if(prices.length == 1){
            return 0;
        }

        // dp[0][i] : i일 때 주식을 사거나 유지할 때 최대 이익
        // dp[1][i] : i일 때 주식을 팔거나 유지할 때 최대 이익
        int [][] dp = new int[2][prices.length];
        for(int i=0; i<prices.length; i++){
            dp[0][i] -= prices[i];
        }

        for(int i=1; i<prices.length; i++){
            // 사거나 유지하거나
            dp[0][i] = Math.max(dp[1][i-1]-prices[i], dp[0][i-1]);
            // 팔거나 유지하거나
            dp[1][i] = Math.max(dp[0][i-1]+prices[i]-fee, dp[1][i-1]);
        }
        return dp[1][prices.length-1] > 0 ? dp[1][prices.length-1] : 0;
    }
}