51.Best Time to Buy and Sell Stock(动态规划)

2024-05-12 01:18

本文主要是介绍51.Best Time to Buy and Sell Stock(动态规划),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

分析:题目要求只能进行一次买卖操作,所以采取动态规划的思想。

sum表示目前已经p[0..i-1]满足条件的最大收益;

low 和 high表示目前已经p[0..i-1]满足条件的买卖价格;

如果新的prices[i]比high大,则将其置为新的high;

prices[i]比low小,则将其置为新的high和low;

拿之前的sum和新生成的high-low的值进行比较,决定是否更新sum的值.

 public int maxProfit(int[] prices) {int len = prices.length;if(len==0){return 0;}int sum = 0;//sum表示目前已经p[0..i-1]满足条件的最大收益int high = prices[0];//low 和 high表示目前已经p[0..i-1]满足条件的买卖价格int low = prices[0];for(int i =1;i<len;i++){if(prices[i]>high){//如果新的prices[i]比high大,则将其置为新的highhigh = prices[i];}else if(prices[i]<low){//prices[i]比low小,则将其置为新的high和lowhigh = prices[i];low = prices[i];}if(sum < high - low){//拿之前的sum和新生成的high-low的值进行比较,决定是否更新sum的值sum = high - low;}}return sum;}

后面做题的时候发现小米2016年校招的题目也用到了这个思想,不同的时候那个题目要求最多可以有两次的买卖操作。

风口之下,猪都能飞。当今中国股市牛市,真可谓“错过等七年”。 给你一个回顾历史的机会,已知一支股票连续n天的价格走势,以长度为n的整数数组表示,数组中第i个元素(prices[i])代表该股票第i天的股价。 假设你一开始没有股票,但有至多两次买入1股而后卖出1股的机会,并且买入前一定要先保证手上没有股票。若两次交易机会都放弃,收益为0。 设计算法,计算你能获得的最大收益。 输入数值范围:2<=n<=100,0<=prices[i]<=100 。

那么题目转化为可以用第i天把所有的n天的股票分开,用left[i]和right[i]表示以第i天分开之后允许买卖一次的最大收益,在左边[0,i]和右边[i+1,len-1]的股票中分别至多买卖一次的收益,即题目转化为用动态规划求在m天内最多只允许买卖一次股票的最大收益。然后比较求得left[i]和right[i]和的最大值。

/*** 计算你能获得的最大收益.* 已知一支股票连续n天的价格走势,以长度为n的整数数组表示,数组中第i个元素(prices[i])代表该股票第i天的股价。* 假设你一开始没有股票,但有至多两次买入1股而后卖出1股的机会,并且买入前一定要先保证手上没有股票。若两次交易机会都放弃,收益为0* * @param prices Prices[i]即第i天的股价* @return 整型*/public int calculateMax(int[] prices) {int len = prices.length;/*left[i]和right[i]表示以第i天分开,在左边[0,i]和右边[i+1,len-1]的股票中分别至多买卖一次的收益,* 即题目转化为用动态规划求在m天内最多只允许买卖一次股票的最大收益*/int[] left = new int[len];int[] right = new int[len];int max = 0;//表示整体的最后整体收益for(int i=0;i<len;i++){left[i] = maxProfit(prices,0,i);right[i] = maxProfit(prices,i+1,len-1);if(max <= left[i]+right[i]){max = left[i]+right[i];}}return max;    	}/*** 计算在数组prices的下标[start,end]对应的股票最多允许买卖一次的最大收益.* 采用动态规划的思想,同leetcode中51.Best Time to Buy and Sell Stock(动态规划)* */public int maxProfit(int[] prices,int start,int end) {int len = end  - start + 1;if(len<=1){return 0;}int sum = 0;//sum表示目前已经p[0..i-1]满足条件的最大收益int high = prices[start];//low 和 high表示目前已经p[0..i-1]满足条件的买卖价格int low = prices[start];for(int i =start+1;i<=end;i++){if(prices[i]>high){//如果新的prices[i]比high大,则将其置为新的highhigh = prices[i];}else if(prices[i]<low){//prices[i]比low小,则将其置为新的high和lowhigh = prices[i];low = prices[i];}if(sum < high - low){//拿之前的sum和新生成的high-low的值进行比较,决定是否更新sum的值sum = high - low;}}return sum;}

这篇关于51.Best Time to Buy and Sell Stock(动态规划)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/981198

相关文章

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

python中time模块的常用方法及应用详解

《python中time模块的常用方法及应用详解》在Python开发中,时间处理是绕不开的刚需场景,从性能计时到定时任务,从日志记录到数据同步,时间模块始终是开发者最得力的工具之一,本文将通过真实案例... 目录一、时间基石:time.time()典型场景:程序性能分析进阶技巧:结合上下文管理器实现自动计时

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表(routes)1.2 修改角色与路由权限表(role_routes)二、后端接口设计

前端 CSS 动态设置样式::class、:style 等技巧(推荐)

《前端CSS动态设置样式::class、:style等技巧(推荐)》:本文主要介绍了Vue.js中动态绑定类名和内联样式的两种方法:对象语法和数组语法,通过对象语法,可以根据条件动态切换类名或样式;通过数组语法,可以同时绑定多个类名或样式,此外,还可以结合计算属性来生成复杂的类名或样式对象,详细内容请阅读本文,希望能对你有所帮助...

Nginx实现动态封禁IP的步骤指南

《Nginx实现动态封禁IP的步骤指南》在日常的生产环境中,网站可能会遭遇恶意请求、DDoS攻击或其他有害的访问行为,为了应对这些情况,动态封禁IP是一项十分重要的安全策略,本篇博客将介绍如何通过NG... 目录1、简述2、实现方式3、使用 fail2ban 动态封禁3.1 安装 fail2ban3.2 配

Vue3中的动态组件详解

《Vue3中的动态组件详解》本文介绍了Vue3中的动态组件,通过`component:is=动态组件名或组件对象/component`来实现根据条件动态渲染不同的组件,此外,还提到了使用`markRa... 目录vue3动态组件动态组件的基本使用第一种写法第二种写法性能优化解决方法总结Vue3动态组件动态