309. Best Time to Buy and Sell Stock with Cooldown (Medium)

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

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

  • You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
  • After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

Input: [1,2,3,0,2]
Output: 3 
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Solutions

class Solution {

    // FIXME This problem is not easy to understand.

    public int maxProfit(int[] prices) {
        if (prices.length == 0 || prices.length == 1) {
            return 0;
        }

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

        maxProfit[0] = 0;
        maxProfit[1] = Math.max(0, prices[1] - prices[0]);

        // profit can be calculated by sellPrice - buyPrice
        // variable value represents the best buy price, it should be the smaller one.
        int value = Math.max(-prices[0], -prices[1]);

        for (int i = 2; i < prices.length; i++) {
            // if sell on ith day, tmp is the floating profit
            int tmp = prices[i] + value;

            // no need to sell
            if (tmp <= maxProfit[i - 1]) {
                maxProfit[i] = maxProfit[i - 1];
            }
            // sell it on ith day because profit increases
            else {
                maxProfit[i] = tmp;
            }

            // but if the profit of the (i-1)th day is larger than sell it today, sell it on (i-1)th
            // day, then buy it today.
            if (maxProfit[i - 2] > tmp) {
                value = maxProfit[i - 2] - prices[i];
            }
        }

        return maxProfit[prices.length - 1];
    }
}

Incorrect Solutions

class Solution {

    // Another Dynamic Programming problem.
    Map<String, Integer> maxx = new HashMap<>();

    public int maxProfit(int[] prices) {
        return recurse(prices, 0, true, -1);
    }

    private int recurse(int[] prices, int day, boolean canBuy, int strikePrice) {
        /*
        // if strike price -1, no stock bought or all sold.
        if (strikePrice != -1) {
            canBuy = false;
        }
        // no stock bought and last time just sold
        else if (!canBuy) {
            canBuy = true;
        }
        // else canBuy = true, keep the original value
        */

        if (day == prices.length) {
            // even with condition strikePrice > 0 which means you have unsold stocks, return 0.

            return 0;
        }

        String key = day + "#" + strikePrice + "#" + canBuy;
        if (maxx.containsKey(key)) {
            return maxx.get(key);
        }

        // You are allowed to buy
        if (canBuy) {
            // 1. buy it
            int rst1 = recurse(prices, day + 1, false, prices[day]);

            // 2. do not buy it
            int rst2 = recurse(prices, day + 1, true, -1);

            maxx.put(key, Math.max(rst1, rst2));
        }
        // Not allowed to buy and you already bought
        else if (strikePrice != -1){

            // 1. sell it
            int rst1 = recurse(prices, day + 1, false, -1) + prices[day] - strikePrice;

            // 2. keep it
            int rst2 = recurse(prices, day + 1, false, strikePrice);

            maxx.put(key, Math.max(rst1, rst2));
        }
        // Not allowed to buy, just sold last yesterday
        else {
            int rst1 = recurse(prices, day + 1, true, strikePrice);

            maxx.put(key, rst1);
        }

        return maxx.get(key);
    }
}

References

  1. https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/discuss/?currentPage=1&orderBy=oldest_to_newest&query=
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:17

results matching ""

    No results matching ""