(笔试题)风口的猪-中国牛市
中国 笔试 风口
2023-09-14 09:00:36 时间
题目:
风口之下,猪都能飞。当今中国股市牛市,真可谓“错过等七年”。 给你一个回顾历史的机会,已知一支股票连续n天的价格走势,以长度为n的整数数组表示,数组中第i个元素(prices[i])代表该股票第i天的股价。 假设你一开始没有股票,但有至多两次买入1股而后卖出1股的机会,并且买入前一定要先保证手上没有股票。若两次交易机会都放弃,收益为0。 设计算法,计算你能获得的最大收益。 输入数值范围:2<=n<=100,0<=prices[i]<=100
输入例子:
3,8,5,1,7,8
输出例子:
12
思路:
1、动态规划
i表示第i天,k表示第k次交易
- 状态转移方程:
- pmax = max{ f(j,k-1)+prices[i]-prices[j] } (0<=j<i)}
- f(i,k) = max{ f(i-1,k), pmax}
- 即f(i,k ) = max{ f(i-1,k) , max { f(j,k-1) + prices[i]-prices[j] | 0<=j<i } }
- f(i-1,k)表示第i天不交易
- max{ f(j,k-1)+prices[i]-prices[j] } (0<=j<i)}表示第i天卖,而这次交易的买应该来自第j天,f(j,k-1) +prices[i] - prices[j] ,0<=j<i ,取最大值。
- max{ f(j,k-1)+prices[i]-prices[j] } (0<=j<i)},这一步可以通过单调队列来优化,可以参考一下:http://www.cnblogs.com/ka200812/archive/2012/07/11/2585950.html,简单的来说,就是将方程中包含j的部分单独拿出来处理,即max(f(j,k-1)-prices[j])
2、前缀、后缀数组
通过前缀数组A来计算0次或1次交易的最大收益;
通过后缀数组B来计算0次或1次交易的最大收益;
通过遍历0-n,计算max(A[i]+B[i])即为最大收益;
代码:
1、简单的动态规划
class Solution { public: /** * 计算你能获得的最大收益 * * @param prices Prices[i]即第i天的股价 * @return 整型 */ int kTransaction(vector<int> prices,int k){ int n=prices.size(); vector<vector<int> > dp(n,vector<int>(k+1,0)); int mx; for(int i=1;i<n;i++){ for(int t=1;t<=k;t++){ mx=dp[i-1][t]; for(int j=i-1;j>=0;j--) mx=max(mx,dp[j][t-1]+prices[i]-prices[j]); dp[i][t]=mx; } } return dp[n-1][k]; } int calculateMax(vector<int> prices) { return kTransaction(prices,2); } };
2、单调队列优化的动态规划
class Solution { public: /** * 计算你能获得的最大收益 * * @param prices Prices[i]即第i天的股价 * @return 整型 */ int kTransaction(vector<int> prices,int k){ int n=prices.size(); vector<vector<int> > dp(n,vector<int>(k+1,0)); vector<int> pMax(k+1,0); int mx; for(int i=0;i<=k;i++) pMax[i]=-prices[0]; for(int i=1;i<n;i++){ pMax[0]=max(pMax[0],dp[i][0]-prices[0]); for(int t=1;t<=k;t++){ mx=dp[i-1][t]; mx=max(mx,pMax[t-1]+prices[i]); pMax[t-1]=max(pMax[t-1],dp[i][t-1]-prices[i]); dp[i][t]=mx; } } return dp[n-1][k]; } int calculateMax(vector<int> prices) { return kTransaction(prices,2); } };
3、前缀后缀数组
class Solution { public: /** * 计算你能获得的最大收益 * * @param prices Prices[i]即第i天的股价 * @return 整型 */ int calculateMax(vector<int> prices) { int n=prices.size(); vector<int> leftMax(n); vector<int> rightMax(n); int lmin=prices[0]; leftMax[0]=0; for(int i=0;i<n;i++){ lmin=min(lmin,prices[i]); leftMax[i]=max(leftMax[i-1],prices[i]-lmin); } int rmax=prices[n-1]; rightMax[n-1]=0; for(int i=n-2;i>=0;i--){ rmax=max(rmax,prices[i]); rightMax[i]=max(rightMax[i+1],rmax-prices[i]); } int pmax=0; for(int i=0;i<n;i++) pmax=max(pmax,leftMax[i]+rightMax[i]); return pmax; } };
相关文章
- 中国继美国之后成功研制千万亿次超级计算机
- 怎样在中国消灭IE6浏览器
- PHP 获取中国时间,即上海时区时间
- 阿里云 OAM 入选「2020中国技术力量年度榜单」,定义云原生应用交付标准
- 中国大数据市场规模分析及预测
- (纪录片)鸟瞰中国 China from Above
- 1.3 中国云创行业地图
- 2016年北京中国云计算技术大会见闻
- 3 中国云栖趋势—3.1 视觉革命
- 【阿里云资讯】云计算再下一城 阿里云携手中国化工集团
- 中国省份数据库+世界国家名数据库
- 【2017中国大学生程序设计竞赛 - 网络选拔赛】Palindrome Function
- AI+5G:2019.03.31第11届中国(深圳)IT领袖峰会【IT新未来: 5G与人工智能】内容概要
- Paper:论文解读《Adaptive Gradient Methods With Dynamic Bound Of Learning Rate》中国本科生提出AdaBound的神经网络优化算法
- pyecharts第十节、地图(二、中国地图)
- 【人工智能AI :Open AI】我想写一本书,书名是《中国文学史》,帮我列一下目录,细化到三级目录,不少于2000字。
- 中国及国外菜系汇总字段
- mySQl该数据库不能将中国的做法
- 中国空气质量在线监測分析平台
- 《Swift程序设计语言》中国翻译和学习笔记page23
- 开源中国 ThinkPHP 领奖
- BC:带你温习并解读《中国区块链技术和应用发展白皮书》—区块链典型应用场景
- 聚焦技术创新实力,时序数据库 TDengine 荣登中国技术先锋年度评选两大榜单