Best Time to Buy and Sell Stock III(JAVA)-动态规划

题目:
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 at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

翻译:
有一个数组表示股票每天的价格,你总共可以交易两次,但每次只能买一支或者卖一支股票,且手上最多只能拥有一支股票,即在买第二支股票前,必须先将第一支股票卖出。设计一个算法,求最大收益

例如,数组 prices = {3,2,6,5,0,3}表示股票每天的价格,则最大收益为:(6-2) +(3-0)=7;

思路:
1、假设只能交易一次,求出每天之前的最大收益,用数组Profit表示,例如针对以上价格,可计算出Profit={0,0,4,4,4,4}
2、用1中的方法,从后往前计算最大收益 reverseProfit={4,4,3,3,3,0}
3、对数组进行prices循环,计算Profit[i]+reverseProfit[i]的最大值,即为最大收益

代码(java)

public class Solution {
    public int maxProfit(int[] prices) {
        int nLen = prices.length;
        if(nLen<2){
            return 0;
        }
        int[] Profit = new int[nLen];
        int minPrice = prices[0];
        int maxProfit = 0;
        for(int i = 1; i<nLen; i++){      //计算买一次卖一次的最大收益
            if(prices[i] < minPrice){
                Profit[i] = Profit[i-1];
                minPrice = prices[i];
            }else{
                int temp = prices[i] - minPrice;
                Profit[i] = Profit[i-1] > temp ? Profit[i-1] : temp;
            }
        }

        if(nLen == 2){   //如果只有三天数据,则只能交易一次,就不进行下面的计算了
            return Profit[1];
        }

        int maxPrice = prices[nLen-1];
        int[] reverseProfit = new int[nLen];
        for(int i = nLen-1; i > 1; i--){//逆向求出交易一次的最大收益
             if(prices[i-1] > maxPrice){
                 reverseProfit[i-1] = reverseProfit[i];
                 maxPrice = prices[i-1];
             }else{
                 int temp = maxPrice - prices[i-1];
                 reverseProfit[i-1] = reverseProfit[i] > temp ? reverseProfit[i] : temp;
             }
        }
        for(int i = 0; i<nLen; i++){     
            int temp = Profit[i] + reverseProfit[i];
            maxProfit = maxProfit > temp ? maxProfit : temp; 
        }
        return maxProfit;
    }
}

搜寻到的改进版(代码更简单,空间复杂度降低):

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){                              
            release2 = Math.max(release2, hold2+i);    
            hold2    = Math.max(hold2,    release1-i);  
            release1 = Math.max(release1, hold1+i);   
            hold1    = Math.max(hold1,    -i);         
        }
        return release2; 
    }
}