文档章节

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

B
 BlueWoods
发布于 2016/08/17 10:16
字数 667
阅读 159
收藏 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
保本基金的核心投资策略,你也能学会

引子 保本基金是指在一个保本周期到期时,投资者可以收回本金、同时获得风险资产投资收益的基金产品。由于具有不论市场如何下跌都不会亏损的特性,保本基金受到了既希望投资于股票之类的风险...

杨博理
2017/09/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

区块链入门教程以太坊源码分析ethdb源码分析

兄弟连区块链入门教程以太坊源码分析ethdb源码分析,2018年下半年,区块链行业正逐渐褪去发展之初的浮躁、回归理性,表面上看相关人才需求与身价似乎正在回落。但事实上,正是初期泡沫的渐退...

兄弟连区块链入门教程
7分钟前
0
0
Eclipse下忽略掉node_modules目录相关配置

https://blog.csdn.net/yzf913214/article/details/72872523

张宏亮1982
8分钟前
0
0
在Python-dataframe中如何把出生日期转化为年龄?

我们在做数据挖掘项目或大数据竞赛时,如果个体是人的时候,获得的数据中可能有出生日期的Series,举个简单例子,比如这样的一些数: # -*- coding: utf-8 -*- import pandas as pd from ...

Mr_zebra
10分钟前
0
0
Android入门—activity生命周期

activity生命周期如下所示: onCreate()方法 创建activity时使用onStart()方法 当activity界面变为用户可见时调用onResume()方法 当activity界面获取到焦点时调用(界面按钮可点击,...

haoyuehong
12分钟前
0
0
使用C++ Builder 6编译产生错误

错误提示: [C++ Error] E2075 Incorrect project override option: Files\Borland\CBuilder6\lib\vcl60.csm[C++ Error] E2075 Incorrect project override option: Files\Borland\CBuilde......

simpower
15分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部