LCR 188. 买卖芯片的最佳时机

解题思路：

设共有 $n$ 天，第 $a$ 天买，第 $b$ 天卖，则需保证 $a < b$ ；可推出交易方案数共有：

$$ (n - 1) + (n - 2) + \cdots + 2 + 1 = n(n - 1) / 2 $$

因此，暴力法的时间复杂度为 $O(n^2)$ 。考虑使用动态规划降低时间复杂度。

动态规划解析：

• 状态定义： 设动态规划列表 $dp$ ，$dp[i]$ 代表以 $prices[i]$ 为结尾的子数组的最大利润（以下简称为 前 $i$ 日的最大利润 ）。
• 转移方程： 由于题目限定 “买卖该芯片一次” ，因此前 $i$ 日最大利润 $dp[i]$ 等于前 $i - 1$ 日最大利润 $dp[i-1]$ 和第 $i$ 日卖出的最大利润中的最大值。

$$ dp[i] = \max(dp[i - 1], prices[i] - \min(prices[0:i])) \ \uparrow \ 前 i 日最大利润 = \max(前 (i-1) 日最大利润, 第 i 日价格 - 前 i 日最低价格) $$

• 初始状态： $dp[0] = 0$ ，即首日利润为 $0$ ；
• 返回值： $dp[n - 1]$ ，其中 $n$ 为 $dp$ 列表长度。

{:align=center width=550}

时间优化：

前 $i$ 日的最低价格 $\min(prices[0:i])$ 时间复杂度为 $O(i)$ 。而在遍历 $prices$ 时，可以借助一个变量（记为成本 $cost$ ）每日更新最低价格。优化后的转移方程为：

$$ dp[i] = \max(dp[i - 1], prices[i] - \min(cost, prices[i]) $$

空间优化：

由于 $dp[i]$ 只与 $dp[i - 1]$ , $prices[i]$ , $cost$ 相关，因此可使用一个变量（记为利润 $profit$ ）代替 $dp$ 列表。优化后的转移方程为：

$$ profit = \max(profit, prices[i] - \min(cost, prices[i]) $$

<,,,,,,,>

代码：

class Solution:
    def bestTiming(self, prices: List[int]) -> int:
        cost, profit = float("+inf"), 0
        for price in prices:
            cost = min(cost, price)
            profit = max(profit, price - cost)
        return profit

class Solution {
    public int bestTiming(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for(int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }
}

class Solution {
public:
    int bestTiming(vector<int>& prices) {
        int cost = INT_MAX, profit = 0;
        for(int price : prices) {
            cost = min(cost, price);
            profit = max(profit, price - cost);
        }
        return profit;
    }
};

复杂度分析：

• 时间复杂度 $O(N)$ ： 其中 $N$ 为 $prices$ 列表长度，动态规划需遍历 $prices$ 。
• 空间复杂度 $O(1)$ ： 变量 $cost$ 和 $profit$ 使用常数大小的额外空间。