只能买卖两次股票的情况下,如何最大化收益
只能买卖两次股票的情况下,如何最大化收益
BlueWoods 发表于1年前
只能买卖两次股票的情况下,如何最大化收益
  • 发表于 1年前
  • 阅读 47
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云实验室 1小时搭建人工智能应用,让技术更容易入门 免费体验 >>>   

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

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

给定一个股票价格(按日期排序)的列表,在最多可以买卖两次的情况下,如何最大化收益;

比如:1, 2, 1, 3, 0, 4;

最大收益为6,在第三天买入,第四天卖出,第五天买入,第六天卖出;

先用动态规划的算法;用f(i, j) 表示在第i (from 0) 天到第j天,只买卖一次时的最大收益;那么,要计算买卖两次的收益,只需要找到一天k,使得f(0, k) + f(k + 1, n - 1)最大即可;

f(i, j) 是以下各式中的最大值:

  1. 0; 如果第i天的价格高于第j天的价格,则不做交易收益最大;
  2. prices(j) - prices(i); 第j天的价格减去第i天的价格;
  3. f(i + 1, j); 第i天不做交易,第i + 1天到第j天交易的最大收益;
  4. f(i, j - 1); 

以下是主要的实现代码:

func maxProfit(prices []int) int {
	prices = compact1(prices)
	prices = compact2(prices)
	if len(prices) == 0 {
		return 0
	}
	n := len(prices)
	fx := make([][]int, n)

	for i := range fx {
		fx[i] = make([]int, n)
	}

	for k := 1; k < n; k++ {
		for i := 0; i+k < n; i++ {
			j := i + k
			fx[i][j] = max(0, prices[j]-prices[i])
			if k == 1 {
				continue
			}
			fx[i][j] = max(fx[i][j], fx[i+1][j])
			fx[i][j] = max(fx[i][j], fx[i][j-1])
		}
	}

	r := fx[0][n-1]
	for k := 1; k < n-1; k++ {
		if fx[0][k]+fx[k][n-1] > r {
			r = fx[0][k] + fx[k][n-1]
		}
	}

	return r
}

 

因为数据可能会很多,在处理之前,先对数据进行了压缩,只保留那些会影响收益的数据;比如1, 2, 3, 4,只需要保留1, 4; 4, 3, 2, 1 只需要保留4, 1;

这个算法的时间复杂度是o(n * n), 空间也需要o(n * n);

但这个题目还有更精简更快速也更优美的算法,令人印象深刻;具体的讨论可以参考 https://discuss.leetcode.com/topic/32288/2ms-java-dp-solution;

使用以下四个值表示当前的状态:

firstBuy: 第一次买入股票的收益;这个值表示为价格的负数,所以价格越低,收益越高;

firstSell: 第一次卖出股票的收益;firstSell = max(firstSell,  firstBuy + currentPrice); 卖出时的价格(加上)第一次买入时的收益(负值);

secondBuy: 第二次买入股票时的收益;secondBuy = max(secondBuy, firstSell - currentPrice);

secondSell: 第二次卖出时的收益;secondSell = max(secondSell, secondBuy + currentPrice);

 代码实现:


func maxProfit2(prices []int) int {
	firstBuy, firstSell := math.MinInt32, 0
	secondBuy, secondSell := math.MinInt32, 0

	for _, price := range prices {
		if firstBuy < -price {
			firstBuy = -price
		}

		if firstSell < firstBuy+price {
			firstSell = firstBuy + price
		}

		if secondBuy < firstSell-price {
			secondBuy = firstSell - price
		}

		if secondSell < secondBuy+price {
			secondSell = secondBuy + price
		}
	}

	return secondSell
}

 

 

标签: leetcode go dp
共有 人打赏支持
粉丝 3
博文 32
码字总数 20281
×
BlueWoods
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: