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

Leave a comment

August 21, 2016 by oneOokay

Best Time to Buy and Sell Stocks I: 最多只能完成一次交易/买卖一次.

  • Kadane’s Algorithm: 把array转换成一个新的Array Diff:
    • Diff[i]表示: 在A[i]买入,A[i+1]卖出所得的收益值.
    • 这样就转换成了求Diff中的一个max sum subarray了.
    • curMaxSum: curMaxSum = curMaxSum > 0 ? curMaxSum + array[i] : array[i].
    • globalMaxSum: 自身和curMaxSum的最大值. (globalMaxSum初始值为0).
  • 找min值(势差):一遍for loop, 一个值存从第一个值到当前值([0, i])中的min,一个值存目前为止的最大收益.
    • 每读入一个数,如果它>min,求差值.更新maxProfit.
    • 如果它小于min,更新min.
  • Brutal : 两遍for循环 O(n^2)
//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 getMaxSum(diff);
    }   
    public int getMaxSum(int[] array){
        int curSumMax = array[0];
        int res = Math.max(0, array[0]);
        for (int i = 1; i < array.length; i ++){              curSumMax = curSumMax >= 0? curSumMax + array[i] : array[i];
            res = Math.max(curMax, res);
        }
        return res;
    }
//简化合并版的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;
 }
//求势差:
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; }

Best Time to Buy and Sell Stocks II: (没有手续费)可以进行多次买卖,但买入前必须卖出。求总的最大收益。

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

Best Time to Buy and Sell Stock with Transaction Fee: 每一次卖出要交手续费,可以任意次交易.求受益最大.

两种DP方法:

  1. 4个状态4个array. length = prices.length
    • buy[i]:在i-th天进行buy操作的总体最大收益.
    • sell[i]:在i-th天进行sell操作的总体最大收益.
    • hold[i]:在i-th天手里头持有1股股票时候且不进行buy和sell的总体最大收益
    • skip[i]:在i-th天手里头不持有任何股票时候且不进行buy和sell的总体最大收益.
  2. 所以递推公式是:
    1. buy[i] = Math.max(skip[i-1], sell[i – 1]) – prices[i]. 为第i-1天不持有股票和卖出股票的收益的较大者 减去 买入股票的钱. 这样决定了在卖出之后才能买入.
    2. sell[i] = Math.max(buy[i – 1], hold[i – 1]) + prices[i] – fee; 为第i-1天买入股票和hold股票的较大值 加上 卖出股票的前 再减去transaction fee
    3. hold[i] = Math.max(hold[i – 1], buy[i – 1]); 为第i-1天持有股票(i天不做任何动作)和第i-1天买入股票的较大值.
    4. skip[i] = Math.max(sell[i – 1], skip[i – 1]); 为第i-1天没有持有股票(i天不作任何动作)和第i-1天卖出股票的较大值.
  3. 初始化:
    1. buy[0] = 0 – prices[0];
    2. 另一个要初始化的值是hold[0]. 因为sell和hold都要依赖于前一个hold的值.buy[0]是负值, hold[0]可以为Integer.Min_VALUE或者buy[0]. 这里hold[0]可以为最小值,因为不存在hold[i] – x的运算,否则的话会overflow,则只能够把hold[0] = buy[0]. (比如第二种dp).
  4. 最终取sell和skip和0的最大值.

第二种dp:

  1. 两种状态: hold和unhold: int[prices.length] 与上面的四种状态对照:
    • hold: 包括当天买入股票当天持有股票不做任何其他动作.
    • unhold:包括当天卖出股票当天不持有股票不做任何其他动作.
  2. 递推公式:
    • hold[i] = Math.max(hold[i – 1], notHold[i – 1] – prices[i]); i天hold为i-1天持有股票 与 第i-1天不持有股票i天买入 的值的较大值.
    • notHold[i] = Math.max(notHold[i – 1], hold[i – 1] + prices[i] – fee); 为i-1天不持有股票 与 第i – 1天持有股票i天卖出股票减去transaction fee的 较大值.
  3. 初始化: Hold[0] = 0 – prices[0].
  4. 最终返回notHold[len – 1]0的较大值.
    public int maxProfit(int[] prices, int fee) {
        if (prices== null || prices.length <= 1)
            return 0;
        int len = prices.length;
        int[] buy = new int[len], hold = new int[len], sell = new int[len], skip = new int[len];
        buy[0] = 0 - prices[0];
        hold[0] = Integer.MIN_VALUE;
        for (int i = 1; i < len; i ++){
            buy[i] = Math.max(sell[i - 1], skip[i - 1]) - prices[i];
            sell[i] = Math.max(buy[i - 1], hold[i - 1]) + prices[i] - fee;
            hold[i] = Math.max(hold[i - 1], buy[i - 1]);
            skip[i] = Math.max(sell[i - 1], skip[i - 1]);
        }
        int res = Math.max(0, sell[len - 1]);
        res = Math.max(skip[len - 1], res);
        return res;
    }

  public int maxProfit(int[] prices, int fee) {
 if (prices== null || prices.length <= 1)
 return 0;
 int len = prices.length;
 int[] notHold = new int[len], hold = new int[len];
 hold[0] = 0 - prices[0];
 for (int i = 1; i < len; i ++){
 hold[i] = Math.max(hold[i - 1], notHold[i - 1] - prices[i]);
 notHold[i] = Math.max(notHold[i - 1], hold[i - 1] + prices[i] - fee); 
 }
 int res = Math.max(notHold[len - 1], 0);
 return res;
 }

Best Time to buy and sell stocks with COOLDOWN: 可以进行多次买卖,买入之前必须卖出.卖出之后的第一天不能继续买入.求最大收益.

套用上面的四个状态:四个array: sell, buy, hold和skip, length = prices.length递推方程是:

  • buy[i] = skip[i – 1] – prices[i]; buy i只能在i-1为skip的时候才能买.
  • sell[i] = Math.max(buy[i – 1], hold[i – 1]) + prices[i]; sell i为i-1买或者hold的较大值+买股票收益.
  • hold[i] = Math.max(buy[i – 1], hold[i – 1]);hold i为 i-1 hold或者买的较大值.
  • skip[i] = Math.max(skip[i – 1], sell[i – 1]); skip i为i-1 skip或者卖的较大值.

初始化: buy[0]和hold[0]都为0 – prices[0]

最终返回skip和sell和0的较大值.

  public int maxProfit(int[] prices) {
 if (prices == null || prices.length <= 1)
 return 0;
 int len = prices.length;
 int[] buy = new int[len], sell = new int[len], hold = new int[len], skip = new int[len];
 buy[0] = 0 - prices[0];
 hold[0] = buy[0];
 for(int i = 1; i < len; i ++){
 buy[i] = skip[i - 1] - prices[i];
 sell[i] = Math.max(buy[i - 1], hold[i - 1]) + prices[i];
 hold[i] = Math.max(buy[i - 1], hold[i - 1]);
 skip[i] = Math.max(skip[i - 1], sell[i - 1]);
 }
 int res = Math.max(0, sell[len - 1]);
 res = Math.max(res, skip[len - 1]);
 return res;
 }

Best Time to Buy and Sell Stocks III: 只能最多进行两次买卖,买入前必须卖出.求max profit。

DP四种状态: hold1, notHold1, hold2, notHold2: length= prices.length

  • hold1[i]表示在i处第一次hold股票的最大值,所以包括了在i处买入: hold1[i] = Math.max(hold1[i – 1], 0 – prices[i]); 为i-1的时候hold,i不作任何事的值 与 在i处第一次买入 的较大值.(这个array是一个min(0 – prices[i])的array, 仅依赖于prices.)
  • notHold1[i]表示在i处第一次股票卖出的空窗期,所以包括了在i处卖出:notHold1[i] = Math.max(notHold1[i – 1], hold1[i – 1] + prices[i]); 为i-1的时候notHold,i不做任何事情的继续nothold的值 与 在i处卖出持有的股票的收益 的较大值. (notHold1的最终值就是仅进行1次交易所得的max profit, 该array仅依赖于hold1)
  • hold2[i]表示在i处第二次hold股票的最大值:hold2[i] = Math.max(hold2[i – 1], notHold1[i – 1] – prices[i]);为 i – 1的时候第二次hold股票,i不作任何事情继续hold的值 与 notHold1 i-1的时候i处进行第二次买入时候的收益 的较大值. (依赖于当前prices[i]的值和前一次nothold的maxProfit)
  • nothold2[i]表示在i处第二次的股票卖出的空窗期.nothold2[i] = Math.max(nothold2[i – 1], hold2[i – 1] + prices[i]);为 i-1的时候的第二次卖出的空窗期,i的时候什么都不干的值 与 i-1第二次hold股票,i处卖出的收益的较大值.(notHold2包含了notHold1的max值)(我觉得还要再研究一下…)

初始化: hold1[0]为0 – prices[0], hold2[i]也要初始化为0 – prices[0]. e.g. corner case[1, 2]

结果返回0和nothold2[len – 1]的较大值.

  public int maxProfit(int[] prices) {
 if(prices == null || prices.length <= 1)
 return 0;
 int len = prices.length;
 int[] hold1 = new int[len], notHold1 = new int[len], 
hold2 = new int[len], notHold2 = new int[len];
 hold1[0] = 0 - prices[0];
 notHold2[0] = 0 - prices[0];
 for(int i = 1; i < len; i ++){
 hold1[i] = Math.max(hold1[i - 1], 0 - prices[i]);
 notHold1[i] = Math.max(notHold1[i - 1], hold1[i - 1] + prices[i]);
 hold2[i] = Math.max(hold2[i - 1], notHold1[i - 1] - prices[i]);
 notHold2[i] = Math.max(notHold2[i - 1], hold2[i - 1] + prices[i]); 
 }
 return Math.max(0, notHold2[len - 1]);
 }

Best Time to Buy and Sell Stocks IV: 限定最多可以做k次交易,求最大的profit。
两个状态: hold和notHold
hold[i][j]表示:在i天的时候进行最多j次完整transaction且持有股票时的maxProfit
notHold[i][j]表示:在i天的时候进行最多j次完整transaction且不持有股票时的maxProfit.
递推公式:
hold[i][j] = Math.max(hold[i – 1][j], notHold[i – 1][j] – prices[i]);
i天不做任何事情,继续持有已有的股票, transaction数目不变: hold[i][j] = hold[i – 1][j]
i天买入股票(这里定义为买入不算一个完整的transaction)(那么i-1天必定为notHold): hold[i][j] = notHold[i-1][j] – prices[i]

notHold[i][j] = Math.max(hold[i – 1][j – 1] + prices[i], notHold[i – 1][j]);
i天不做任何事情,继续不持有股票, transaction数目不变: notHold[i][j] = notHold[i – 1][j]
i天卖出持有的股票(完整的transaction + 1)(那么i-1天必定为hold,且hold的transaction次数应该为j – 1次): notHold[i][j] = hold[i – 1][j – 1] + prices[i]

需要初始化的值有:
hold[0][j] (hold[i – 1][j]) : 第0天第j次transaction hold股票的maxProfit为 0 – prices[0].
hold[i][0] (hold[i – 1][j – 1]) : 第i天第0次transaciton hold股票的maxProfix为 max(0 – prices[i]) i = [0, i].
notHold[0][j] (notHold[i – 1][j]) : 第0天第j次transaction不持有股票 maxProfix是0.

且由定义: 当第一次买入还没有卖出的时候的transaction次数为0,卖出之后transaction次数才变为1. 所以array是int[prices.length][k + 1].

最终返回notHold[prices.length – 1][k].

public int maxProfit(int k, int[] prices) {
	if (prices == null || prices.length <= 1)
 		return 0; 
	int len = prices.length;
 	//如果可以进行的交易数目大于len/2的话那么等同于Best time to buy and sell stocks II.
 	if (k > len / 2) return getMax(prices);
	
	//hold[i][j] : i天 j次 transaction maxProfit
	int[][] hold = new int[len][k + 1];
	int[][] notHold = new int[len][k + 1];
	for(int i = 0; i < len; i ++) 
		hold[i][0] = Math.max(0 - prices[i], hold[i - 1][0]);
	for(int i = 0; i <= k; i ++){
		hold[0][i] = 0 - prices[0];
		notHold[0][i] = 0;
	}
	//这里互换i,j的话一样的
	for (int j = 1; j <= k; j ++){
		for(int i = 1; i < len; i ++){
			hold[i][j] = Math.max(hold[i - 1][j], notHold[i - 1][j] - prices[i]);
			notHold[i][j] = Math.max(hold[i - 1][j - 1] + prices[i], notHold[i - 1][j]);
		}
	}
	return notHold[len - 1][k];
}
    
private int getMax(int[] prices){
	int res = 0;
	for (int i = 1; i < prices.length; i ++){
 		if (prices[i] - prices[i - 1] > 0)
			res += prices[i] - prices[i - 1];
	}
	return res;
}
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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s

%d bloggers like this: