目录1. 最佳买卖股票时机含冷冻期题目描述题解2. 买卖股票的最佳时机 III题目描述题解1. 最佳买卖股票时机含冷冻期 题目描述 给定一个整数数组prices,其中第prices[
给定一个整数数组prices
,其中第prices[i]
表示第i
天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
力扣链接
我们用 dp[i]
表示第 i
天结束之后的「累计最大收益」。根据题目描述,由于我们最多只能同时买入(持有)一支股票,并且卖出股票后有冷冻期的限制,因此我们会有三种不同的状态:
dp[i][0]
;f[i][1]
;f[i][2]
。如何进行状态转移呢?在第 i 天时,我们可以在不违反规则的前提下进行 买入 或者 卖出 操作,此时第 i 天的状态会从第 i−1 天的状态转移而来;我们也可以不进行任何操作,此时第 i 天的状态就等同于第 i−1 天的状态。那么我们分别对这三种状态进行分析:
对于 dp[i][0]
,我们目前持有的这一支股票可以是在第 i−1
天就已经持有的,对应的状态为 f[i−1][0]
;或者是第 i
天买入的,那么第 i-1
天就不能持有股票并且不处于冷冻期中,对应的状态为 dp[i−1][2]
加上买入股票的负收益 prices[i]
。因此状态转移方程为:dp[i][0]=max(dp[i−1][0], dp[i−1][2]−prices[i])
对于 dp[i][1]
,我们在第 i
天结束之后处于冷冻期的原因是在当天卖出了股票,那么说明在第 i−1
天时我们必须持有一支股票,对应的状态为 dp[i−1][0]
加上卖出股票的正收益 prices[i]
。因此状态转移方程为:dp[i][1]=dp[i−1][0]+prices[i]
对于 dp[i][2]
,我们在第 i
天结束之后不持有任何股票并且不处于冷冻期,说明当天没有进行任何操作,即第 i-1
天时不持有任何股票:如果处于冷冻期,对应的状态为 dp[i−1][1]
;如果不处于冷冻期,对应的状态为 dp[i−1][2]
。因此状态转移方程为:dp[i][2]=max(dp[i−1][1],dp[i−1][2])
这样我们就得到了所有的状态转移方程。如果一共有 n
天,那么最终的答案即为:max(dp[n−1][0],dp[n−1][1],dp[n−1][2])
注意到如果在最后一天(第 n−1
天)结束之后,手上仍然持有股票,那么显然是没有任何意义的。因此更加精确地,最终的答案实际上是 dp[n-1][1]
和 dp[n-1][2]
中的较大值,即:max(dp[n−1][1],dp[n−1][2])
注意到上面的状态转移方程中,dp[i][..]
只与 dp[i-1][..]
有关,而与 dp[i-2][..]
及之前的所有状态都无关,因此我们不必存储这些无关的状态。也就是说,我们只需要将 dp[i-1][0]
,dp[i−1][1]
,dp[i-1][2]
存放在三个变量中,通过它们计算出 dp[i][0]
,dp[i][1]
,dp[i][2]
并存回对应的变量,以便于第 i+1
天的状态转移即可。
var maxProfit = function(prices) {
const length = prices.length;
let [dp0, dp1, dp2] = [-prices[0], 0, 0];
for(let i = 1; i < length; i++) {
let newDp0 = Math.max(dp0, dp1 - prices[i]);
let newDp1 = Math.max(dp1, dp2);
let newDp2 = dp0 + prices[i];
dp0 = newDp0;
dp1 = newDp1;
dp2 = newDp2;
}
return Math.max(dp1, dp2);
};
给定一个数组,它的第 i
个元素是一支给定的股票在第 i
天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例1:
输入:prices = [3,3,5,0,0,3,1,4]
输出:6
解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。
随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。
示例 2:
输入:prices = [1,2,3,4,5]
输出:4
解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例 3:
输入:prices = [7,6,4,3,1]
输出:0
解释:在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4:
输入:prices = [1]
输出:0
力扣链接
每一天结束之后,有可能处于以下五种状态之一:
我们可以遍历 prices
数组,模拟第 i 天的情况。计算出第 i 天五种情况利润的最大值。
prices[0]
至 prices[i]
的最小值,假设为 buy1
。可以看做,第二种情况利润的最大值为:-buy1
。状态转移方程为:buy1 = max(buy1, -prices[i]);
prices[i]
的时候,判断要不要卖出。如果在以最小的亏损买入第一支股的情况下,卖出当前这支股所得利润最大,则卖出当前这支股。状态转移方程为:sell1 = max(sell1, prices[i] + buy1);
注意这里是 prices[i] + buy1
,不是 prices[i] - buy1
,因为 buy1
是负值,代表利润。prices[i]
的时候,判断要不要买入。如果在卖出第一支股所得利润最大的情况下,买入当前这支股最终所得利润最大,则买入当前这支股。状态转移方程为:buy2 = max(buy2, sell1 - prices[i]);
prices[i]
的时候,判断要不要卖出。如果在卖出第一支股然后买入第二支股所得利润最大的情况下,卖出当前这支股所得利润最大,则卖出当前这支股。状态转移方程为:sell2 = max(sell2, prices[i] + buy2);
最终的 sell2
就是我们要的答案。
var maxProfit = function (prices) {
const n = prices.length;
let buy1 = -prices[0];
let sell1 = 0;
let buy2 = -prices[0];
let sell2 = 0;
for (let i = 1; i < n; i++) {
buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, prices[i] + buy1);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, prices[i] + buy2);
}
return sell2;
};
到此这篇关于javascript股票的动态买卖规划实例分析下篇的文章就介绍到这了,更多相关js股票内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: JavaScript股票的动态买卖规划实例分析下篇
本文链接: https://www.lsjlt.com/news/172049.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
2024-01-12
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0