Best Time to Buy and Sell Stock III, Leetcode 解题笔记

在Best Time to Buy and Sell Stock II的基础上又加了限制,最多只能买卖两次股票,并且手上最多也只能持有一支股票。既然最多只能完成两笔交易,而且还不重叠,那么就先想一个暴力的方法,从0~n-1,针对每一个i,我们看子序列prices[0,..,i]和prices[i,…,n-1]上分别只作一次交易取得的最大收益(即版本一Best Time to Buy and Sell Stock)。这样的思路也可以理解为分治算法,时间复杂度为O(N^2)。

在这个思想的基础上进行改进,即动态规划保留之前的结果。分两次扫描,第一次从左向右,先计算子序列[0,…,i]中的最大收益,第二次从右向左,计算子序列中[i,…,n-1]上的最大收益,结合这两部的结果就能得到最终的的最大收益了。这个过程中正向、逆向扫描和嘴和整合都是O(N)的时间复杂度。
https://chazyhabit.wordpress.com/2014/08/22/best-time-to-buy-and-sell-stock-iii-leetcode-134/

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<=1) return 0;
        int len = prices.length;
        int[] historyPro = new int[len];
        historyPro[0] = 0;
        int lowest = prices[0];
        // from left to right
        for(int i=1;i<len;++i) {
            lowest = Math.min(lowest, prices[i]);
            historyPro[i] = Math.max(historyPro[i-1], prices[i]-lowest);
        }
        int[] futurePro = new int[len];
        futurePro[len-1] = 0;
        int highest = prices[len-1];
        // from right to left
        for(int i=len-2;i>=0;--i) {
            highest = Math.max(highest, prices[i]);
            futurePro[i] = Math.max(futurePro[i+1], highest-prices[i]);
        }
        // add two transactions
        int maxPro = 0; // test case: 1 2
        for(int i=0;i<len;i++)
            maxPro = Math.max(maxPro, historyPro[i]+futurePro[i]);
        return maxPro;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s