买卖芯片的最佳时机
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 44 ms, 内存: 17.8 MB
/*
* 思路:
* 使用Java Stream来实现上述逻辑。
* 我们可以使用一个自定义的类来在流中传递当前的最低价格和最大利润。
*/
import java.util.stream.IntStream;
public class Solution {
public int maxProfit(int[] prices) {
class State {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
}
State state = new State();
IntStream.of(prices).forEach(price -> {
state.minPrice = Math.min(state.minPrice, price);
state.maxProfit = Math.max(state.maxProfit, price - state.minPrice);
});
return state.maxProfit;
}
}
解释
方法:
这个题解使用了动态规划的思想来解决问题。我们定义 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)
代码细节讲解
🦆
为什么在定义`dp[i][1]`时使用`-prices[i-1]`而不是`prices[i-1]`?这样的定义是如何体现买入芯片的成本的?
▷🦆
题解中的状态转移方程`dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1])`中,`dp[i-1][1] + prices[i-1]`代表什么意义?
▷🦆
在动态规划数组初始化时,为什么`dp[0][1]`被初始化为负无穷?这样的初始化有什么特殊的意义?
▷