Skip to content
New issue

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

121. 买卖股票的最佳时机 #45

Open
webVueBlog opened this issue Sep 4, 2022 · 0 comments
Open

121. 买卖股票的最佳时机 #45

webVueBlog opened this issue Sep 4, 2022 · 0 comments

Comments

@webVueBlog
Copy link
Owner

121. 买卖股票的最佳时机

Description

Difficulty: 简单

Related Topics: 数组, 动态规划

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0

示例 1:

输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

示例 2:

输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0。

提示:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

Solution

Language: JavaScript

/**
 * @param {number[]} prices
 * @return {number}
 */
// 买入卖出各一次
//  贪心
// var maxProfit = function(prices) {
//     if (prices.length === 0) return 0

//     let min = prices[0]
//     let max = 0

//     for (let p of prices) {
//         min = Math.min(min, p)
//         max = Math.max(max, p - min)
//     }

//     return max
// }

// 动态规划 时间复杂度O(n) 空间复杂度O(n),dp数组第二维是常数
var maxProfit = function(prices) {
    let n = prices.length
    let dp = new Array(n).fill(0).map(() => 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]
}

// 压缩空间
// var maxProfit = function(prices) {
//     let n = prices.length
//     let dp = Array.from(new Array(n), () => new Array(2))

//     dp[0] = 0
//     dp[1] = -prices[0]

//     for (let i = 1; i < n; i++) {
//         dp[0] = Math.max(dp[0], dp[1] + prices[i])
//         dp[1] = Math.max(dp[1], -prices[i])
//     }
//     return dp[0]
// }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant