714. Best Time to Buy and Sell Stock with Transaction Fee

 一刷 07/2022

Version #2 Better DP with two states

不是特别理解

Time O(N)

Space O(1)

Runtime: 4 ms, faster than 90.39% of Java online submissions for Best Time to Buy and Sell Stock with Transaction Fee.

Memory Usage: 76.1 MB, less than 31.51% of Java online submissions for Best Time to Buy and Sell Stock with Transaction Fee.

class Solution {

    public int maxProfit(int[] prices, int fee) {

        int cash = 0;

        int hold = -prices[0];

        for (int i = 1; i < prices.length; i++) {

            cash = Math.max(cash, hold + prices[i] - fee);

            hold = Math.max(hold, cash - prices[i]);

        }

        return cash;

    }

}

Version #1 DP with max previous profit

Time O(N)

Space O(N)

Runtime: 9 ms, faster than 46.70% of Java online submissions for Best Time to Buy and Sell Stock with Transaction Fee.

Memory Usage: 70.1 MB, less than 68.66% of Java online submissions for Best Time to Buy and Sell Stock with Transaction Fee.

class Solution {

    public int maxProfit(int[] prices, int fee) {

        int[] dp = new int[prices.length];

        int prevMax = -prices[0] - fee;

        // dp[i] - max profix that can achieve on day i

        for (int i = 1; i < prices.length; i++) {

            prevMax = Math.max(prevMax, (i >= 2 ? dp[i - 2] : 0) - prices[i - 1] - fee);

            dp[i] = Math.max(dp[i - 1], prices[i] + prevMax);

        }

        return dp[prices.length - 1];

    }

}