Ricky.L的随笔
0%

LeetCode.120.三角形最小路径和（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.121.买卖股票的最佳时机（简单）

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

题解

解法1

设dp[i]为第0天到第i天获取最大利润。

在第i天，可以选择不卖股票或卖出股票。

  1. 不卖股票，dp[i] = dp[i - 1]
  2. 卖出股票，由于只能买入一次和卖出一次，那要获得最大利润，肯定要在第0天到第i -1中股票最低的时候买入，dp[i] = prices[i] - minPrice

dp[i]只与上一个状态有关，所以可以用变量存储状态，不需要数组记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    fun maxProfit(prices: IntArray): Int {
        val n = prices.size
        if (n <= 1) return 0
        var maxProfit = 0
        var minPrice = prices[0]
        for (i in 1 until n) {
            maxProfit = maxOf(maxProfit, prices[i] - minPrice)
            minPrice = minOf(minPrice, prices[i])
        }
        return maxProfit
    }
}

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    fun maxProfit(prices: IntArray): Int {
        if (prices.isEmpty()) return 0
        val n = prices.size
        // dp[i][k]表示前i天持有和未持有第i天的股票的最大收益
        val dp = Array(n) { IntArray(2) { 0 } }
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        for (i in 1 until n) {
            // 第i天未持有，可能是前i-1天就未持有然后今天不操作，或者以前持有了今天卖出了
            dp[i][0] = maxOf(dp[i - 1][0], dp[i - 1][1] + prices[i])
            // 第i天持有，可能是前i-1天就持有了然后今天不操作，或者以前就未持有今天买入了
            dp[i][1] = maxOf(dp[i - 1][1], -prices[i])
        }
        return dp[n - 1][0]
    }
}