动态规划之求解股市的最大利润问题

Posted by Jerry on May 31, 2017

股市中给你至多一次交易机会,两次机会,k次机会,任意次数,以及有限制的买进和卖出,分别求最大的利润

Say you have an array for which the ith element is the price of a given stock on day i. 个人做题代码

121.Best Time to Buy and Sell Stock

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit. 至多一次交易 可以参考我的个人做题记录121,里面还有按类别分类的题目。

Solution 1

题目给定股市的每天价格,判断哪天买进哪天卖出能挣最多。先将价格转换为与之前一天的差值然后只需要求最大连续子数组。

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null||prices.length==1||prices.length==0)return 0;
        int[] a = new int[prices.length-1];
        for (int i = 0; i < a.length; i++) {
            a[i]=prices[i+1]-prices[i];
        }
        int max = 0;
        int cur = 0;
        for (int i = 0; i < a.length; i++) {
            cur = Math.max(0, cur+a[i]);
            max = Math.max(max, cur);
        }
        return max;
    }
}

Solution2

该解法来自discuss,思路和我的一样,代码非常简洁。常数的空间复杂度

public class Solution {
    public int maxProfit(int[] prices) {
        int maxCur = 0, maxSoFar = 0;
        for(int i = 1; i < prices.length; i++) {
            maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);
            maxSoFar = Math.max(maxCur, maxSoFar);
        }
        return maxSoFar;
    }
}

122. Best Time to Buy and Sell Stock II

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). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). 任意次数,但只能卖掉之后买进

public class Solution {
    public int maxProfit(int[] prices) {
       int len = prices.length, profit = 0;
        for (int i = 1; i < len; i++)
            if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        return profit; 
    }
}

123. Best Time to Buy and Sell Stock III

You may complete at most two transactions. 至多两次交易

Solution 1

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null||prices.length<=1)return 0;
        else {
            int k = 2;
            int[][] dp = new int[k+1][prices.length];
            int res = 0;
            for (int i = 1; i <= k; i++) {
                int tmpMax = - prices[0];
                for (int j = 1; j < prices.length; j++) {
                    dp[i][j] = Math.max(dp[i][j-1], prices[j] + tmpMax);
                    //i-1次交易的可能为最大值,下面这两行居然是等价的,但dp[i-1][j]比较好理解,在j天卖出后买上买进,而不是在j-1天卖出,j天买进
                    //tmpMax = Math.max(tmpMax, dp[i-1][j] - prices[j]);
                    tmpMax = Math.max(tmpMax, dp[i-1][j-1] - prices[j]);
                    res = Math.max(dp[i][j], res);
                }
            }
            return res;
        }
    }
}

Solution 2

public class Solution {
    public int maxProfit(int[] prices) {
        int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE;
        int release1 = 0, release2 = 0;
        for(int i:prices){                              // Assume we only have 0 money at first
            release2 = Math.max(release2, hold2+i);     // The maximum if we've just sold 2nd stock so far.
            hold2    = Math.max(hold2,    release1-i);  // The maximum if we've just buy  2nd stock so far.
            release1 = Math.max(release1, hold1+i);     // The maximum if we've just sold 1nd stock so far.
            hold1    = Math.max(hold1,    -i);          // The maximum if we've just buy  1st stock so far. 
        }
        return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1.
    }
}

188.Best Time to Buy and Sell Stock IV

You may complete at most k transactions. 至多k次交易

Solution 1 (Memory Limit Exceeded)

超时或者内存超出的原因在于当k>=prices.length/2的时候,那么就相对于可以任意交易次数,直接求出最大利润即可。见方法二

public class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices==null||prices.length<=1)return 0;
        else {
            int[][] dp = new int[k+1][prices.length];
            int res = 0;
            for (int i = 1; i <= k; i++) {
                int tmpMax = - prices[0];
                for (int j = 1; j < prices.length; j++) {
                    dp[i][j] = Math.max(dp[i][j-1], prices[j] + tmpMax);
                    //i-1次交易的可能为最大值
                    tmpMax = Math.max(tmpMax, dp[i-1][j] - prices[j]);
                    res = Math.max(dp[i][j], res);
                }
            }
            return res;
        }
    }
}

Solution 2

public class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices==null||prices.length<=1)return 0;
        int len = prices.length;
        if (k >= len / 2) return quickSolve(prices);
        int[][] t = new int[k + 1][len];
        for (int i = 1; i <= k; i++) {
            int tmpMax =  -prices[0];
            for (int j = 1; j < len; j++) {
                t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax);
                tmpMax =  Math.max(tmpMax, t[i - 1][j - 1] - prices[j]);
            }
        }
        return t[k][len - 1];
    }
    private int quickSolve(int[] prices) {
        int len = prices.length, profit = 0;
        for (int i = 1; i < len; i++)
            // as long as there is a price gap, we gain a profit.
            if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        return profit;
    }
}

309. Best Time to Buy and Sell Stock with Cooldown

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)

给你任意次交易次数,但是不能买进后立即买进,要休息一天后才能买进

Solution 1

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices==null||prices.length<=1)return 0;
        int k = (prices.length+1)/3;
        int[][] dp = new int[k+1][prices.length];
        for (int i = 1; i < k + 1; i++) {
            int tmpMax = - prices[0];
            for (int j = 1; j < prices.length; j++) {
                // 要么第j次cooldownday,或者就卖出
                dp[i][j] = Math.max(dp[i][j-1], tmpMax+prices[j]);
                //第j次卖出,如果前面j>1,不能用dp[i-1][j-1],因为这样就违反规定
                if(j>1)
                    tmpMax = Math.max(tmpMax, dp[i-1][j-2]-prices[j]);
                else
                    tmpMax = Math.max(tmpMax,dp[i-1][j-1] - prices[j]);
            }
        }
        return dp[k][prices.length-1];
    }
}

Solution 2

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length < 2){
            return 0;
        }
        int len = prices.length;
        int[] sell = new int[len]; //sell[i] means must sell at day i
        int[] cooldown = new int[len]; //cooldown[i] means day i is cooldown day
        sell[1] = prices[1] - prices[0];
        for(int i = 2; i < prices.length; ++i){
            cooldown[i] = Math.max(sell[i - 1], cooldown[i - 1]);
            sell[i] = prices[i] - prices[i - 1] + Math.max(sell[i - 1], cooldown[i - 2]);
        }
        return Math.max(sell[len - 1], cooldown[len - 1]);
    }
}

Solution 3

具体解释见discuss

public int maxProfit(int[] prices) {
    int sell = 0, prev_sell = 0, buy = Integer.MIN_VALUE, prev_buy;
    for (int price : prices) {
        prev_buy = buy;
        buy = Math.max(prev_sell - price, prev_buy);
        prev_sell = sell;
        sell = Math.max(prev_buy + price, prev_sell);
    }
    return sell;
}