程序人生|漫画:程序教你寻找股票买入卖出的最佳时机(动态规划)( 四 )
本文插图
F(2,3)= max(F(1,2)-2 , F(1,3))= max(-2 , -1)= -1 , 所以第2行第4列的结果是-1:
本文插图
F(2,4)= max(F(1,3)+2 , F(1,4))= max(1 , 0)= 1 , 所以第2行第5列的结果是1:
本文插图
接下来我们继续根据状态转移方程式 , 填充第3行的数据:
本文插图
接下来填充第4行:
本文插图
以此类推 , 我们一直填充完整个表格:
本文插图
如图所示 , 表格中最后一个数据13 , 就是全局的最大收益 。
本文插图
本文插图
//最大买卖次数
private static int MAX_DEAL_TIMES = 2;
public static int maxProfitFor2Time(int[] prices) {
if(prices== || prices.length==0) {
return 0;
}
//表格的最大行数
int n = prices.length;
//表格的最大列数
int m = MAX_DEAL_TIMES*2+1;
//使用二维数组记录数据
int resultTable = new int[n][m];
//填充初始状态
resultTable[0][1] = -prices[0];
resultTable[0][3] = -prices[0];
//自底向上 , 填充数据
for(int i=1;i
for(int j=1;j
if((j&1) == 1){
resultTable[i][j] = Math.max(resultTable[i-1][j], resultTable[i-1][j-1]-prices[i]);
}else {
resultTable[i][j] = Math.max(resultTable[i-1][j], resultTable[i-1][j-1]+prices[i]);
}
}
}
//返回最终结果
return resultTable[n-1][m-1];
}
本文插图
本文插图
本文插图
本文插图
本文插图
- 北青网综合|婴儿泳池溺水获救,家长索赔150万 店家:愿走法律程序
- 证券日报之声|蚂蚁集团启动退款程序 投资者表示有遗憾但可以理解
- 中年|“蚂蚁”启动退款程序,上交所最新回应
- 趣头条|最新进展!蚂蚁集团A股今天启动退款程序!证监会、上交所深夜发声
- 超美时尚屋|蚂蚁团体将于11月6日启动退款程序! 上交所: 尊重并支持蚂蚁团体决定
- 蚂蚁ipo|蚂蚁IPO启动退款程序,5只“蚂蚁配售”基金将申请上市转型LOF
- 环球网|上海迪士尼回应APP被工信部通报:系假冒应用程序
- 企业|企业投资(程序化)决策与非程序化决策
- 北京日报|“北京政务服务”小程序服务突破1000项,覆盖“衣食住行”
- 红星新闻|1024程序员节,祝所有程序员永不脱发、永无bug!