文档章节

只能买卖两次股票的情况下,如何最大化收益

B
 BlueWoods
发布于 2016/08/17 10:16
字数 667
阅读 108
收藏 0

原题见: 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
}

 

 

© 著作权归作者所有

共有 人打赏支持
B
粉丝 2
博文 39
码字总数 21286
作品 0
杭州
量化交易策略的研发流程

新书《中低频量化交易策略研发(上)》免费发布也没多少人看,很是捉急。借着专栏宣传一下,下面的内容来自原书第二章。 这里在精炼量化交易策略基本研发结构的基础上,通过介绍有限的几个组...

杨博理
2016/01/08
0
0
场内货币基金投资交易攻略:所有产品对比

场内货币基金投资交易攻略:所有产品对比 http://finance.sina.com.cn/money/fund/20140509/190119060209.shtml 2014年05月09日 19:01 新浪财经 微博 我有话说(76人参与) 收藏本文 基金百宝箱...

wowotuo
04/24
0
0
对冲基金有哪些类型,有哪些基本手段?

什么是对冲基金?对冲基金,也称避险基金或套利基金,是指由金融期货和金融期权等金融衍生工具与金融组织结合后以高风险投机为手段并以盈利为目的的金融基金。它是投资基金的一种形式,属于免...

chen_h
2017/12/10
0
0
【腾讯Bugly干货分享】程序员们也该知道的事——“期权和股票”

本文来自于腾讯Bugly公众号(weixinBugly),未经作者同意,请勿转载,原文地址:https://mp.weixin.qq.com/s/pfj9NLLuKYAfJJF84R9WAw 作者:Bugly 精神哥 导语 今年的双十一,腾讯18周年司庆...

腾讯Bugly
2016/12/19
41
0
【1-4】区块链量化投资系列课程 - 动态平衡策略

NO.1 QUANT.LA 量化干货聚集地 宽客在线 沃伦 · 巴菲特的导师本杰明 · 格雷厄姆曾经在《聪明的投资者》一书中,曾经提到过一种股票债券动态平衡的交易模式。 这种交易模式非常简单: 把手中...

发明者量化FMZ
前天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

java并发备忘

不安全的“先检查后执行”,代码形式如下: if(条件满足){ //这里容易出现线程安全问题//doSomething}else{//doOther} 读取-修改-写入 原子操作:使用CAS技术,即首先从V中读取...

Funcy1122
今天
0
0
SpringBoot2.0 停机

最近新建了个SpringBoot2.0的项目,因为原来一直使用的是传统的Tomcat部署war包的形式,所以这次SpringBoot内置Tomcat部署jar包的时候遇到了很多问题。其中一个就是因为没有外置的Tomcat容器...

Canaan_
昨天
0
1
Confluence 6 外部参考

一个外部参考的意思是任何站点链接到你 Confluence 的实例。任何时候当 Confluence 的用户单击这个外部链接的时候,Confluence 可以记录这次单击为参考。 在默认的情况下,外部链接的参考链接...

honeymose
昨天
0
0
Android中的设计模式之抽象工厂模式

参考 《设计模式解析》 第十一章 Abstract Factory模式 《设计模式:可复用面向对象软件的基础 》3.1 Abstract Factory 抽象工厂 对象创建型模式 《Android源码设计模式解析与实战》第6章 创...

newtrek
昨天
0
0
Redis | 地理空间(GEO)的一个坑

Redis的地理空间(Geo)是个好东西,轻轻松松的就可以把地图描点的问题处理了, 最近却遇到一个坑...Redis采用的Msater-Slave模式, 运用GEORADIUS在salve读取对应的数据,新增了从节点但是从不返...

云迹
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部