JavaScript股票买卖算法实战：从单利到动态规划

1. 买卖股票的最佳时机（单次交易）

题目背景与目标

给定一个数组 prices，其中第 i 个元素表示一支给定股票第 i 天的价格。你需要选择一天买入并在未来某一天卖出，以计算所能获取的最大利润。如果不能获取任何利润，则返回 0。

核心思路：贪心策略

目标是找到两个数，使差值最大且小的数在左边。我们不需要构建复杂的利润数组，只需在遍历过程中记录出现过的最低价格 start，并实时计算当前价格与最低价格的差值作为当前最大利润 profit。

• 初始化 start 为第一天价格，profit 为 0。
• 遍历每一天，更新 start 为当前最低价。
• 更新 profit 为当前差价与历史最高利润的较大值。

代码实现

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  const length = prices.length;
  let start = prices[0], profit = 0;
  for(let i = 1; i < length; i++) {
    start = Math.min(start, prices[i]);
    profit = Math.max(profit, prices[i] - start);
  }
  return profit;
};

2. 买卖股票的最佳时机 II（多次交易）

题目背景与目标

在每一天，你可以决定是否购买和/或出售股票，但任何时候最多只能持有一股股票。你可以在同一天买入并卖出。求能获得的最大利润。

核心思路：动态规划

定义两个状态变量来代替二维数组，从而降低空间复杂度：

• dp0：表示第 i 天交易完后手里持有股票的最大利润。
• dp1：表示第 i 天交易完后手里没有股票的最大利润。

状态转移方程

• dp0 = Math.max(dp0, dp1 - prices[i])：今天持有股票，可能是昨天就持有，也可能是昨天没持有今天买入。
• dp1 = Math.max(dp1, dp0 + prices[i])：今天没持有股票，可能是昨天就没持有，也可能是昨天持有今天卖出。

代码实现

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  const length = prices.length;
  // 初始状态：第0天持有股票花费了prices[0]，不持有则为0
  let dp0 = -prices[0];
  let dp1 = 0;
  
  for(let i = 1; i < length; i++) {
    // 注意：计算dp1时应使用上一轮的dp0，但在JS中顺序执行需注意逻辑准确性。
    // 此处逻辑基于上一轮结果推导今日状态
    let newDp0 = Math.max(dp0, dp1 - prices[i]);
    let newDp1 = Math.max(dp1, dp0 + prices[i]);
    
    dp0 = newDp0;
    dp1 = newDp1;
  }
  
  return dp1;
};

最终答案即为 dp1，因为全部交易结束后，不持有股票的收益一定高于或等于持有股票的收益。

3. 买卖股票的最佳时机含手续费

题目背景与目标

与多次交易类似，但可以无限次完成交易。关键在于每笔交易（买入并卖出）都需要支付固定的手续费 fee。求获得利润的最大值。

核心思路：带手续费的动态规划

状态定义与前题一致：dp0 为持有股票的最大利润，dp1 为不持有股票的最大利润。

变化点

只有在卖出时（从不持有变为持有再变回不持有，或者更准确地说是执行卖出动作）才需要扣除手续费。因此在计算 dp1 时，需要从卖出收益中减去 fee。

• dp0 = Math.max(dp0, dp1 - prices[i])：买入操作不涉及手续费。
• dp1 = Math.max(dp1, dp0 + prices[i] - fee)：卖出操作涉及手续费，需减去 fee。

代码实现

/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
    const length = prices.length;
    let [dp0, dp1] = [-prices[0], 0];
    
    for(let i = 0; i < length; i++) {
        // 临时变量保存上一轮状态，确保逻辑正确
        let prevDp0 = dp0;
        
        dp0 = Math.max(dp0, dp1 - prices[i]);
        dp1 = Math.max(dp1, prevDp0 + prices[i] - fee);
    }
    
    return dp1;
};

总结

以上三种场景展示了从简单贪心到动态规划的递进过程。对于单次交易，记录最低点即可；对于多次交易，通过维护持有和非持有两个状态来模拟每日决策；当引入手续费时，仅在卖出环节增加成本判断。这些算法均能在 O(n) 时间复杂度内高效求解。

以上就是JavaScript股票买卖算法实战的详细内容，更多关于JavaScript动态规划算法的资料请关注本站其它相关文章！