Best Time to Buy and Sell Stock III

Question

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

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.

Example

Given an example [4,4,6,1,1,4,2,5], return 6.

Analysis

一种算法比较容易想到： 找寻一个点j，将原来的prices[0..n-1]分割为prices[0..j]和prices[j..n-1]，分别求两段的最大profit。 内层循环与Best Time to Buy and Sell Stock相同，为O(n), 外层循环为O(n)，记录不同的j两段maxProfit的值需要O(n)空间，因此总体时间复杂度为O(n^2)，空间复杂度为O(n)。

改进（参考pickless的讲解）: 对于点j+1，求prices[0..j+1]的最大profit时，很多工作是重复的，在求prices[0..j]的maxProfit中已经计算过了。 类似于Best Time to Buy and Sell Stock，可以在O(1)的时间从prices[0..j]推出prices[0..j+1]的最大profit。 但是如何从prices[j..n-1]推出prices[j+1..n-1]？反过来思考，我们可以用O(1)的时间由prices[j+1..n-1]推出prices[j..n-1]。 最终算法： 数组l[i]记录了prices[0..i]的最大profit， 数组r[i]记录了prices[i..n]的最大profit。 已知l[i]，求l[i+1]是简单的，同样已知r[i]，求r[i-1]也很容易。 最后，我们再用O(n)的时间找出最大的l[i]+r[i]，即为题目所求。 这样时间复杂度O(n), 空间复杂度O(n)

参考 http://blog.csdn.net/fightforyourdream/article/details/14503469

状态机State Machine：

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/149383/Easy-DP-solution-using-state-machine-O(n)-time-complexity-O(1)-space-complexity

这种想法很神奇：

// Assume we are in state S
// If we buy, we are spending money but we can also choose to do nothing
// Doing nothing means going from S->S
// Buying means going from some state X->S, losing some money in the process
S = max(S, X-prices[i])

// Similarly, for selling a stock
S = max(S, X+prices[i])

Java Implementation

public class Solution {
    int maxProfit(int[] prices) {
    if(prices == null || prices.length == 0) return 0;
    int s1=-prices[0], s2=Integer.MIN_VALUE,s3=Integer.MIN_VALUE,s4=Integer.MIN_VALUE;

    for(int i=1;i<prices.length;++i) {            
        s1 = Math.max(s1, -prices[i]);
        s2 = Math.max(s2, s1+prices[i]);
        s3 = Math.max(s3, s2-prices[i]);
        s4 = Math.max(s4, s3+prices[i]);
    }
    return Math.max(0,s4);
    }
}

Solution

A Intuitive Implementation Using Divide And Conquer

import java.util.*;

public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // find maxProfit for {0, j}, find maxProfit for {j + 1, n - 1}
        // find max for {max{0, j}, max{j + 1, n - 1}}

        if (prices == null || prices.length == 0) {
            return 0;
        }

        int maximumProfit = 0;
        int n = prices.length;

        ArrayList<Profit> preMaxProfit = new ArrayList<Profit>(n);
        ArrayList<Profit> postMaxProfit = new ArrayList<Profit>(n);
        for (int i = 0; i < n; i++) {
            preMaxProfit.add(maxProfitHelper(prices, 0, i));
            postMaxProfit.add(maxProfitHelper(prices, i + 1, n - 1));
        }
        for (int i = 0; i < n; i++) {
            int profit = preMaxProfit.get(i).maxProfit + postMaxProfit.get(i).maxProfit;
            maximumProfit = Math.max(profit, maximumProfit);
        }
        return maximumProfit;
    }

    private Profit maxProfitHelper(int[] prices, int startIndex, int endIndex) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int i = startIndex; i <= endIndex; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            }
            if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
            }
        }
        return new Profit(maxProfit, minPrice);
    }

    public static void main(String[] args) {
        int[] prices = new int[]{4,4,6,1,1,4,2,5};
        Solution s = new Solution();
        System.out.println(s.maxProfit(prices));
    }
};

class Profit {
    int maxProfit, minPrice;
    Profit(int maxProfit, int minPrice) {
        this.maxProfit = maxProfit;
        this.minPrice = minPrice;
    }
}

Another Implementation with Dynamic Programming

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

        int[] left = new int[prices.length];
        int[] right = new int[prices.length];

        // DP from left to right;
        left[0] = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(prices[i], min);
            left[i] = Math.max(left[i - 1], prices[i] - min);
        }

        //DP from right to left;
        right[prices.length - 1] = 0;
        int max = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0; i--) {
            max = Math.max(prices[i], max);
            right[i] = Math.max(right[i + 1], max - prices[i]);
        }

        int profit = 0;
        for (int i = 0; i < prices.length; i++){
            profit = Math.max(left[i] + right[i], profit);  
        }

        return profit;
    }
}

State Machine

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        return maxProfit(prices, 2);
    }
    private int maxProfit(int[] array, int t) {
        int[] stock = new int[t * 2];
        Arrays.fill(stock, Integer.MIN_VALUE);
        stock[0] = -array[0];
        for(int i = 1; i < array.length; ++i) {
            stock[0] = Math.max(stock[0], -array[i]);
            for (int j = 1; j < 2 * t; j += 2) {
                stock[j] = Math.max(stock[j], stock[j - 1] + array[i]);
                if (j + 1 < 2 * t) {
                    stock[j + 1] = Math.max(stock[j + 1], stock[j] - array[i]);
                }
            }
        }
        return Math.max(0, stock[2 * t - 1]);
    }
}

Reference

http://liangjiabin.com/blog/2015/04/leetcode-best-time-to-buy-and-sell-stock.html http://www.jiuzhang.com/solutions/best-time-to-buy-and-sell-stock-iii/