Best Time to Buy and Sell Stocks i-iv+cooldown

Leave a comment

August 21, 2016 by oneOokay

Best Time to Buy and Sell Stocks I:

最多只能完成一次交易/买卖一次


  • Brutal : 两遍for循环 O(n^2)
  • 找min值(势差):一遍for loop, 一个值存从o-i中的min,一个值存目前为止的最大收益.
    • 每读入一个数,如果它>min,求差值.如果差值大于目前的最大收益,更新最大收益值.如果它小于min,更新min.
  • Kadane’s Algorithm: 把array转换成一个新的Array Diff:
    • Diff[i]表示: 在A[i]买入,A[i+1]卖出所得的收益值.
    • 这样就转换成了求B中的一个max sum subarray了.只是要注意globalMax最小值应为0.

求势差:

public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;
        int min = prices[0];//初始化为第一个值
        int max = 0;
        for (int i = 0; i < prices.length; i ++){
            if (prices[i] < min){
                min = prices[i];
            }else {
                max = Math.max(max, prices[i] - min);
            }
        }
        return max;
    }

Kadane’s Algorithm:

    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;
        int n = prices.length;
        int[] diff = new int[n - 1];
        for (int i = 1; i < n; i ++){
            diff[i - 1] = prices[i] - prices[i - 1];
        }
        return maxSubarray(diff);
    }   
    public int maxSubarray(int[] array){
        int curMax = array[0];
        int globalMax = array[0];
        for (int i = 1; i < array.length; i ++){
             curMax = curMax > 0? curMax + array[i] : array[i];
//或者:curMax = Math.max(curMax + array[i], array[i]);
            globalMax = Math.max(curMax, globalMax);
        }
        return Math.max(globalMax, 0);
    }

简化合并版的Kadane’s Algorithm

public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;
        int curMax = 0;
        int globalMax = 0;
        for (int i = 1; i < prices.length; i ++){
//这里因为curMax永远为0或者大于0的数字,所以可以直接加
            curMax += prices[i] - prices[i - 1]; 
            curMax = Math.max(0, curMax);
            globalMax = Math.max(curMax, globalMax);
        }
        return globalMax;
    }

Best Time to Buy and Sell Stocks II:

可以进行多次买卖,但买入前必须卖出。求总的最大收益。


  • 一个上升序列中,分段的差和与头尾差是一样的。所以所有上升子序列的和即为max profit sum。
  • 从I里面的那个Diff array可知,这题就是求Diff array中所有的正数的和.

Best Time to buy and sell stocks will COOLDOWN:

可以进行多次买卖,买入之前必须卖出.卖出之后的第一天不能继续买入.求最大收益.


两种dp方式, 是很好的思维想法的例子:

  1. State Machine Thinking

wvr4tn8

根据描述有以上三种状态, s0, s1, s2. 状态之间的相互转化有cool/buy/sell. 根据这个建立推导公式:

s0[i] = Math.max(s0[i - 1], s2[i - 1]);
s1[i] = Math.max(s1[i - 1], s0[i - 1] - prices[i]);
s2[i] = s1[i - 1] + prices[i]:从s1卖掉股票,赚入prices[i]

代码:

public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int n = prices.length;
        int[] s0 = new int[n];
        int[] s1 = new int[n];
        int[] s2 = new int[n];
        
        s0[0] = 0;
        s1[0] = 0 - prices[0];
        s2[0] = 0;
        
        for (int i = 1; i < n; i ++){
            s2[i] = s1[i - 1] + prices[i];
            s1[i] = Math.max(s0[i - 1] - prices[i], s1[i - 1]);
            s0[i] = Math.max(s0[i - 1], s2[i - 1]);
        }
        return Math.max(s0[n - 1], s2[n - 1]);
    }

优化成int:

public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int n = prices.length;
        int s0 = 0;
        int s1 = 0 - prices[0];
        int s2 = 0;
        int prev_s2 = 0;
        for (int i = 1; i < n; i ++){
            s2 = s1 + prices[i];
            s1 = Math.max(s0 - prices[i], s1);
            s0 = Math.max(s0, prev_s2);
            prev_s2 = s2;
        }
        return Math.max(s0, s2);
    }

2. 也是三个数组,但是是不同的意义,比较难理解一些吧我觉得.我个人更喜欢第一个. https://discuss.leetcode.com/topic/30421/share-my-thinking-process/93

需要维护三个一维数组buy, sell和cool。其中:

  • buy[i]表示在第i天之前最后一个操作是买的最大收益(这个最后的buy的操作可以发生在0-i的任何一天,在该天之后都可看做skip)。
  • sell[i]表示在第i天之前最后一个操作是卖的最大收益。
  • cool[i]表示在第i天之前最后一个操作是冷冻期的最大收益。

递推式为:

buy[i]  = max(cool[i-1] - price, buy[i-1]): 
在i-1天中最后一次操作是cooldown的时候最大收益-付出买股票的钱
在i-1天中最后一次操作是buy的时候,第i天的时候什么都不做.
sell[i] = max(buy[i-1] + price, sell[i-1])
在i-1天中最后一次操作是buy的时候的最大收益+卖出股票赚的钱
在i-1天中最后一次操作是sell的时候的最大收益
cool[i] = max(sell[i-1], cool[i-1])
保证了buy, cool down, buy的情况不会出现

优化:

因为sell[i-1] >= rest[i-1]:所以rest[i] = sell[i – 1],所以可以仅维护sell[] 和 buy[]两个数组

  • buy[i] = Math.max(buy[i – 1], sell[i – 2] – prices[i]);
  • sell[i] = Math.max(buy[i – 1] + prices[i], sell[i – 1]);

从上看出sell依靠于buy[i – 1]和sell[i-1]; buy依靠于:buy[i-1]和sell[i-2],所以进而可以不用数组,只用两个int.

public int maxProfit(int[] prices) {
 if(prices == null || prices.length <= 1) return 0;
 int n = prices.length;
 int sell = 0;
 int buy = 0 - prices[0];
 int prev_sell = 0;//相当于sell[i-1]
 int prev_buy = 0;//相当于buy[i-1]
 for (int i = 1; i < n; i ++){
 prev_buy = buy;
 buy = Math.max(prev_sell - prices[i], prev_buy); //相当于sell[i-2]
 prev_sell = sell; //sell[i-1]
 sell = Math.max(prev_buy + prices[i], prev_sell);
 } 
 return sell;
 }

Best Time to Buy and Sell Stocks III:

只能最多进行两次买卖,买入前必须卖出.求max profit。


用DP进行两次扫描形成两个数组,left[] 用来存从左起至i的max profit;right[]用来存从i至最右的max profit.最后一次对left[]和right[]进行扫描,找出max。(同时其实也是找出第一次和第二次交易的分界线)

public int maxProfit(int[] prices) {
// write your code here
if (prices == null || prices.length <= 1) {
return 0;
}
int len = prices.length;
int[] left = new int[len];
int[] right = new int[len];

left[0] = 0;
int min = prices[0]; //注意初始化不能为0
for (int i = 1; i < len; i ++) {
min = Math.min(prices[i], min); //构建left[]时,从左往右扫,参考best time to buy and sell I; 第一步通过Math.min找出全局最小值,然后在过往的max和当前的price[i] - min 找出较大值(由从左往右扫的方向决定的)。从左往右扫,那么买入的最小值是可以得知的,所以尝试用扫描的值减去买入最小值来求得max profit
left[i] = Math.max(left[i - 1], prices[i] - min);
}

right[len - 1] = 0;
int max = prices[len - 1]; //同样初始化不能为0
for (int i = len - 2;i >= 0; i --) {//构建right[]时,从右往左扫较为方便,反着I来写就可以;区别是第一步通过Math.max找出全局最大值,然后在过往的max和当前的max - prices[i]中找出较大值(由从右往左扫决定的)从右往左扫,那么卖出的最大值是可以得知的,所以尝用卖出的最大值减去扫描的值来的到max profit。
max = Math.max(prices[i], max);
right[i] = Math.max(right[i + 1], max - prices[i]);
}

int profit = Integer.MIN_VALUE;
for (int i = 0; i < len; i ++) {
profit = Math.max(left[i] + right[i], profit);
}
return profit;
}

另外这里有一个大神的

Best Time to Buy and Sell Stocks IV:

终极啊,限定最多可以做k次交易,求最大的profit。k不定的情况下大概只有用dp来做了吧。

结合这两个来看吧:

http://www.cnblogs.com/grandyang/p/4295761.html

http://blog.csdn.net/linhuanmars/article/details/23236995

http://liangjiabin.com/blog/2015/04/leetcode-best-time-to-buy-and-sell-stock.html dp的二维数组可以用一个一位数组来维护。

public int maxProfit(int k, int[] prices) {
if (prices == null || prices.length <= 1) { return 0; } 
int days = prices.length; 
//这里也可以是k >= days/2:因为在给定天数内能做的最大的买卖次数就是days/2
if ( k >= days ) {
return getMaxProfit(prices);
}
//k + 1: 因为要初始化第0次交易,所以size为k+1
int[][] globalbest = new int[days][k + 1]; 
int[][] mustsell = new int[days][k + 1];

//初始化
mustsell[0][0] = globalbest[0][0] = 0;
for (int i = 1; i <= k; i ++){
globalbest[0][i] = mustsell[0][i] = 0; //前0天 N次交易,profit均为0;
globalbest[i][0] = mustsell[i][0] = 0; //前i天,0次交易,profit均为0;
}

for (int i = 1; i < days; i ++) {
int diff = prices[i] - prices[i - 1];
for (int j = 1; j <= k; j ++) {
mustsell[i][j] = Math.max(globalbest[i - 1][j - 1] + diff, mustsell[i - 1][j] + diff); 
//mustsell[i - 1][j] + diff: 这里为j而不是j-1是因为,可以将第j-1天卖出与第j天卖出合并为一次交易。
globalbest[i][j] = Math.max(globalbest[i - 1][j], mustsell[i][j]);

}
}
return globalbest[days - 1][k];
}

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

采用一维数组:

//else dp
int[] globalbest = new int[k + 1];
int[] mustsell = new int[k + 1];

//初始化
mustsell[0] = globalbest[0] = 0;
for (int i = 1; i < days; i ++) { int diff = prices[i] - prices[i - 1]; for (int j = k; j > 0; j --) {
mustsell[j] = Math.max(globalbest[j - 1], mustsell[j] + diff); 
 globalbest[j] = Math.max(globalbest[j], mustsell[j]);

}
}

return globalbest[k];
==================================
算法真是太奇妙了。。。
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

%d bloggers like this: