难度: Medium
数组 prices 记录了某芯片近期的交易价格，其中 prices[i] 表示的 i 天该芯片的价格。你只能选择 某一天 买入芯片，并选择在 未来的某一个不同的日子 卖出该芯片。请设计一个算法计算并返回你从这笔交易中能获取的最大利润。
如果你不能获取任何利润，返回 0。
示例 1：
输入：prices = [3, 6, 2, 9, 8, 5] 输出：7 解释：在第 3 天（芯片价格 = 2）买入，在第 4 天（芯片价格 = 9）卖出，最大利润 = 9 - 2 = 7。
示例 2：
输入：prices = [8, 12, 15, 7, 3, 10] 输出：7 解释：在第 5 天（芯片价格 = 3）买入，在第 6 天（芯片价格 = 10）卖出，最大利润 = 10 - 3 = 7。
提示：
0 <= prices.length <= 10^50 <= prices[i] <= 10^4注意：本题与主站 121 题相同：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
运行时间: 44 ms
内存: 17.8 MB
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# dp[n][k][c] 表示第n天，还有k次交易机会，目前状态是持有还是卖出，最多能获得的利润
# 这道题k = 1
n = len(prices)
dp = [[0, 1] for _ in range(n+1)]
dp[0][0] = 0
dp[0][1] = float('-inf')
for i in range(1, n+1):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]) # 由上一次的卖转移而来
# dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i-1])
dp[i][1] = max(dp[i-1][1], -prices[i-1]) # 由上一次的买转移而来
return dp[-1][0]
if __name__ == '__main__':
s = Solution()
s.maxProfit([7,1,5,3,6,4])
这个题解使用了动态规划的思想来解决问题。我们定义 dp[i][0] 为第 i 天结束时不持有股票所能获得的最大利润，而 dp[i][1] 为第 i 天结束时持有股票所能获得的最大利润。状态转移方程如下：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]) 表示第 i 天不持有股票的情况下，可以是前一天也不持有，或者是前一天持有但在今天卖出。dp[i][1] = max(dp[i-1][1], -prices[i-1]) 表示第 i 天持有股票的情况下，可以是前一天持有，或者是今天新买入股票。
时间复杂度: O(n)
空间复杂度: O(n)，但可优化至 O(1)
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [[0, 1] for _ in range(n+1)]
dp[0][0] = 0
dp[0][1] = float('-inf')
for i in range(1, n+1):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]) # 更新不持有股票的状态
dp[i][1] = max(dp[i-1][1], -prices[i-1]) # 更新持有股票的状态
return dp[-1][0] # 返回最后一天不持有股票的最大利润
if __name__ == '__main__':
s = Solution()
s.maxProfit([7,1,5,3,6,4]) # 示例调用
在动态规划中，`dp[i][1]`代表在第 i 天结束时持有股票所能获得的最大利润。当选择在第 i 天买入股票时，我们必须支付芯片的价格 `prices[i-1]`（因为数组下标从0开始，所以第i天的价格是`prices[i-1]`），这意味着我们的现金会减少。因此，我们使用 `-prices[i-1]` 来更新状态，表示这一天买入股票后的负成本（即现金减少）。这样的定义可以正确反映买入股票时财务状况的变化，即减少了相应的金额。
在这个状态转移方程中，`dp[i-1][1] + prices[i-1]`代表如果前一天（第 i-1 天）持有股票，并且选择在第 i 天卖出股票，所能获得的利润。这里 `dp[i-1][1]` 是第 i-1 天持有股票的最大利润，而 `prices[i-1]` 是第 i 天的股票价格。将这两者相加，就得到了在第 i 天卖出股票后的总利润。这种计算方式帮助确定是否卖出股票在第 i 天能获得更高的利润。
在动态规划中，`dp[0][1]` 被初始化为负无穷是为了正确处理边界情况。`dp[0][1]` 表示在第 0 天结束时持有股票的最大利润，但实际上第 0 天开始时我们还没有进行任何交易，因此不可能持有股票。将其初始化为负无穷可以防止第一天买入股票的情况被错误地忽视或处理，因为任何正数（利润）与负无穷比较时，选取的将是正数，这反映了如果第一天买入股票的情况。这种初始化确保了动态规划的逻辑正确性和算法的有效性。