贪心
解题思路
因为不限制交易次数，只要今天价格比昨天高，就交易，利润为正累加，最后的和就是最大的利润；
收集 正利润 的区间，就是股票买卖的区间，只需要关注最终利润，不需要记录区间；
注意第一天是没有利润的，这道题之所以可以用贪心是因为 局部最优：收集每天的正利润，可以推导出，全局最优：求得最大利润；
图解
复杂度
-
时间复杂度：
O(n)，n 是数组的长度； -
空间复杂度：
O(1)；
代码实现
var maxProfit = function (prices) {
let res = 0;
for (let i = 1; i < prices.length; ++i) {
// 今天价格和昨天的差值是否为正，如果为正累加进去，为负则加 0
res += Math.max(0, prices[i] - prices[i - 1]);
}
return res;
};
动态规划
解题思路
确定 dp 数组以及下标的含义：dp[i][j] 表示天数 [0, i] 区间里，下标 i 这一天状态为 j 的时候能够获得的最大利润，其中：
- j = 0，表示当前不持股；
- j = 1，表示当前持股；
确定递推公式：
- dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])：规定了今天 不持股，有以下两种情况：
- dp[i - 1][0]：昨天不持股，今天什么都不做；
- dp[i - 1][1] + prices[i]：昨天持股，今天卖出股票（现金数增加）；
- dp[i][1] = Math.max(dp[i - 1][1], -prices[i])：规定了今天 持股，有以下两种情况：
- dp[i - 1][1]：昨天持股，今天什么都不做（现金数与昨天一样）；
- dp[i - 1][0] - prices[i]：昨天不持股，今天买入股票（注意：允许交易多次）；
如何初始化 dp 数组：
- 第 0 天不持有：dp[0][0] = 0；
- 第 0 天持有：dp[0][1] = -prices[0]；
确定遍历顺序：从递推公式可以看出 dp[i] 都是由 dp[i - 1] 推导出来的，那么一定是从前向后遍历；
举例推导 dp 数组：以 prices = [7, 1, 5, 3, 6, 4] 为例：
索引 i = 0 索引 i = 1 索引 i = 2 索引 i = 3 索引 i = 4 索引 i = 5 dp[i][0] 规定了今天 不持股 0 0 4 4 7 7dp[i][1] 规定了今天 持股 -7 -1 -1 1 1 3
复杂度
-
时间复杂度：
O(n)； -
空间复杂度：状态压缩之前是
O(n)，状态压缩后是O(1)；
代码实现
JavaScript
JavaScript
// 时间复杂度 O(n) 空间复杂度 O(n)，dp 数组第二维是常数
const maxProfit = function (prices) {
let n = prices.length;
let dp = new Array(n).fill(0).map(it => new Array(2).fill(0));
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]); // 第 i 天，不持有股票，最大值
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); // 第 i 天，持有股票，最大值
}
return dp[n - 1][0];
};
// 状态压缩
const maxProfit = function (prices) {
let n = prices.length;
let dp = new Array(2).fill(0);
dp[0] = 0; // 第一天，不持有股票
dp[1] = -prices[0]; // 第一天，持有股票
for (let i = 1; i < n; i++) {
dp[0] = Math.max(dp[0], dp[1] + prices[i]); // 第 i 天，不持有股票，最大值
dp[1] = Math.max(dp[1], dp[0] - prices[i]); // 第 i 天，持有股票，最大值
}
return dp[0];
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 121. 买卖股票的最佳时机
上一篇
评论
