LeetCode | 122. 买卖股票的最佳时机 II

[aermin]

题目

解法

动态规划

/*
 * @lc app=leetcode.cn id=122 lang=javascript
 * 思路：
 * 买卖最佳时机就看今天和昨天各种操作状态取最大值
 * 可以围绕着今天我有没有持有股票来穷举各种操作，从而取最大值
 * 今天我没有持有股票有两种可能：
 * 1.我昨天没持有，今天不操作
 * 2.我昨天持有，今天卖了
 * 动态方程：dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
 * 今天持有股票有两种可能：
 * 1.我昨天持有，今天不操作
 * 2.我昨天没持有，今天买入
 * 动态方程：dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
 * 这边dp[i][k][0]的值就是我们所要的，因为总盈利就看在最后一天
 * 在不再持有股票的情况下的所有盈利
 * [122] 买卖股票的最佳时机 II
 */

// @lc code=start
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let dp_i_0 = 0, dp_i_1 = -Infinity;
    for(let i = 0; i < prices.length; i++) {
        //dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
        //dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
        const temp = dp_i_0;
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        dp_i_1 = Math.max(dp_i_1, temp - prices[i])
    }
    return dp_i_0;
};

复杂度分析

时间复杂度：O(n)，遍历一次。
空间复杂度：O(1)，需要常量的空间。

简单的一次遍历

连续两个数字之间的差值如果大于0就计入利润，我们获得的总和将是最大利润

/**
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = function(prices) {
    let maxprofit = 0;
    const length = prices.length -1;
    for(let i = 0; i < length; i ++) {
        const difference = prices[i+1] - prices[i]; 
        if(difference > 0) maxprofit = maxprofit + difference;
    }
    return maxprofit;
};

复杂度分析

时间复杂度：O(n)，遍历一次。
空间复杂度：O(1)，需要常量的空间。

reference

题解 作者：LeetCode

一个方法团灭 6 道股票问题 作者：labuladong