动态规划-123-Best Time to Buy and Sell Stock III

Description:
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).

问题描述:
给定一个数组，其中下标i对应的元素为i天的股票额
设计一个算法获取最大利润。你只能完成两次交易。注意，你必须在买进前卖出

解法1:

class Solution {
    public int maxProfit(int[] prices) {
        int sell1 = 0, sell2 = 0, buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;

        for(int price : prices){
            buy1 = Math.max(buy1, -price);
            sell1 = Math.max(sell1, buy1 + price);
            buy2 = Math.max(buy2, sell1 - price);
            sell2 = Math.max(sell2, buy2 + price);
        }

        return sell2;
    }
}

解法2(二维dp):

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n == 0) return 0;

        int[][] dp = new int[3][n];
        for(int i = 1; i <= 2; i++) {
            int balance = -prices[0];
            for(int j = 1; j < n; j++) {
                dp[i][j] = Math.max(dp[i][j - 1], balance + prices[j]);
                balance = Math.max(balance, dp[i - 1][j - 1] - prices[j]);
            }
        }

        return dp[2][n - 1];
    }
}

解法3(一维dp):

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n == 0) return 0;

        int[] dp = new int[n];
        int temp = 0;  
        for(int i = 1; i <= 2; i++) {
            int balance = -prices[0];
            temp = dp[0];
            for(int j = 1; j < n; j++) {
                int copy = dp[j];
                dp[j] = Math.max(dp[j - 1], balance + prices[j]);
                balance = Math.max(balance, temp - prices[j]);
                temp = copy;
            }
        }

        return dp[n - 1];
    }
}

尽管解法1最简洁，我更喜欢解法2和3，因为可以扩展到更一般化的情况，例如k次交易(188. Best Time to Buy and Sell Stock IV)