We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
仰望星空的人,不应该被嘲笑
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。
注意:你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
示例 2:
输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题想了挺久,参考了大佬的题解,典型的二维 dp 问题。
状态 dp[i][j] 表示:在下标为 i 的这一天,用户手上持股状态为 j 所获得的最大利润。
dp[i][j]
i
j
说明:
dp[i][0] 怎样转移?
dp[i][0]
对于当前这天,不持股份的话,当然可以是前一天也没有持股份,即 dp[i-1][0] 还有可能就是昨天持股了,我今天把这股份卖了,那么就要加上今天卖的那份股份值,即 dp[i-1][1] + prices[i]
dp[i-1][0]
dp[i-1][1] + prices[i]
综上,得到状态方程:
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] 怎样转移?
dp[i][1]
对于当前这天,如果持了股份的话,当天可以是前一天也持了股份,即 dp[i-1][1] 还有可能就是我今天才持股,同时注意,我们不能加上 dp[i-1][0],因为我们只能交易一次,即从当前这天持股,那么买入带来的收益即为 -prices[i]
dp[i-1][1]
-prices[i]
dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
/** * @param {number[]} prices * @return {number} */ var maxProfit = function(prices) { let n = prices.length; if(n<2) return 0; // 不足两天,肯定没收益 let dp = new Array(n); for(let i=0;i<n;i++){ dp[i] = new Array(2); } dp[0][0] = 0; // 第一天不持股 dp[0][1] = -prices[0]; // 第一天持股,即买入 for(let i=1;i<n;i++){ dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); dp[i][1] = Math.max(dp[i-1][1], -prices[i]); } return dp[n-1][0]; // 最大收益,最后一天卖出股票的结果 };
文章产出不易,还望各位小伙伴们支持一波!
往期精选:
小狮子前端の笔记仓库
leetcode-javascript:LeetCode 力扣的 JavaScript 解题仓库,前端刷题路线(思维导图)
小伙伴们可以在Issues中提交自己的解题代码,🤝 欢迎Contributing,可打卡刷题,Give a ⭐️ if this project helped you!
访问超逸の博客,方便小伙伴阅读玩耍~
学如逆水行舟,不进则退
The text was updated successfully, but these errors were encountered:
No branches or pull requests
题目描述
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。
注意:你不能在买入股票前卖出股票。
示例 1:
示例 2:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
这道题想了挺久,参考了大佬的题解,典型的二维 dp 问题。
状态
dp[i][j]
表示:在下标为i
的这一天,用户手上持股状态为j
所获得的最大利润。说明:
j
只有 2 个值:0 表示不持股(特指卖出股票以后的不持股状态),1 表示持股。i
的这一天把股票抛售了;dp[i][0]
怎样转移?对于当前这天,不持股份的话,当然可以是前一天也没有持股份,即
dp[i-1][0]
还有可能就是昨天持股了,我今天把这股份卖了,那么就要加上今天卖的那份股份值,即
dp[i-1][1] + prices[i]
综上,得到状态方程:
dp[i][1]
怎样转移?对于当前这天,如果持了股份的话,当天可以是前一天也持了股份,即
dp[i-1][1]
还有可能就是我今天才持股,同时注意,我们不能加上
dp[i-1][0]
,因为我们只能交易一次,即从当前这天持股,那么买入带来的收益即为-prices[i]
综上,得到状态方程:
最后
文章产出不易,还望各位小伙伴们支持一波!
往期精选:
小狮子前端の笔记仓库
leetcode-javascript:LeetCode 力扣的 JavaScript 解题仓库,前端刷题路线(思维导图)
小伙伴们可以在Issues中提交自己的解题代码,🤝 欢迎Contributing,可打卡刷题,Give a ⭐️ if this project helped you!
访问超逸の博客,方便小伙伴阅读玩耍~
学如逆水行舟,不进则退
The text was updated successfully, but these errors were encountered: