- 👉 【LeetCode 直通车】：121 买卖股票的最佳时机（简单）【面试真题】
设定最大值 max 买入点 buy
循环一次 遇到 prices[i] 小于 buy 更新 buyå
比较 prices[i] - buy 与 max 更新 max
javascript
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let len = prices.length;
if(len === 1) return 0;
let max = 0;
let buy = prices[0];
for(let i = 1; i < len; i++) {
if(buy > prices[i]) {
buy = prices[i];
} else {
max = Math.max(max, prices[i] - buy)
}
}
return max;
};多次买入
设定 count 标识 收入 设定 min 当前遍历的最小值
for 循环 当 prices[i] > prices[i+1]
count +=prices[i]-min
当 min > prices[i] 更新 min
javascript
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
const len = prices.length;
let count = 0;
if (len === 1) return count;
let min = prices[0];
for (let i = 1; i < len; i++) {
min = Math.min(min, prices[i])
if (min < prices[i]) {
if (prices[i + 1] < prices[i]) {
count += prices[i] - min;
min = prices[i + 1]
} else if(i === len -1) {
count += prices[i] - min
}
}
}
return count
};第二种：
只要下一次涨前一次铁定买了
javascript
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
let start = prices[0];
let count = 0;
let len = prices.length
for (let i = 0; i < len; i++) {
if (start < prices[i]) {
count += prices[i] - start;
}
start = prices[i]
}
return count
};动态规划来进行状态转移
js
有如下状态
dp[i][0] 第i天结束时，持有股票时的最大收益
dp[i][1] 第i天结束时，不持有股票且明天不可以购买股票时，最大收益
dp[i][2] 第i天结束时，不持有股票且明天可以购买股票时，最大收益
如何转移
dp[i][0] 之前持有 当前买的 之前肯定不是冷冻期
-->
Math.max(dp[i-1][0], dp[i-1][2] - prices[i])
dp[i][1] 所以之前是持有 但是卖掉了
-->
dp[i-1][0] + prices[i]
dp[i][2] 之前就没有
-->
Math.max(dp[i-1][1], dp[i-1][2])
最后手上一定是没有的只需要取 Math.max（dp[i][1] dp[i][2]）
[-prices[0], 0, 0] 开始 然后进行状态转移javascript
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let dp = [-prices[0], 0, 0];
for(let i = 1; i < prices.length; i++) {
const cur = prices[i];
dp = [Math.max(dp[0], dp[2] - cur), dp[0] + cur, Math.max(dp[2], dp[1])]
}
return Math.max(...dp)
};javascript
dp[i][0] 第i天结束时，持有股票时的最大收益
dp[i][1] 第i天结束时，不持有股票时的最大收益
状态转移为
dp[i][0] 前一天就持有， 当天买入
-->
Math.max(dp[i-1][0], dp[i][1] - prices[i])
dp[i][1] 前一天没有 当天卖出
-->
Math.max(dp[i-1][0], dp[i][1] + prices[i] - fee)javacript
/**
* @param {number[]} prices
* @param {number} fee
* @return {number}
*/
var maxProfit = function(prices, fee) {
let [no, yes] = [0, -prices[0]];
for(let i = 1; i < prices.length; i++) {
const cur = prices[i];
no = Math.max(yes + cur - fee, no);
yes = Math.max(yes, no - cur)
}
return no
};javascript
只有两次买入时机
dp[i][0] 第 i 天结束时 有一次买入操作
dp[i][1] 第 i 天结束时 买入一次卖出一次
dp[i][2] 第 i 天结束时 买入两次次卖出一次
dp[i][3] 第 i 天结束时 买入两次次卖出两次次
dp[i][0] 第 i-1 天 购入 一次 第 i 天购入
-->
Math.max(dp[i-1][0], -prices[i])
dp[i][1] 第 i 天 卖出一次 第 i -1 买入一次卖出一次
-->
Math.max(dp[i][0] + prices[i], dp[i-1][1])
dp[i][2] 第 i 天结束时买入 前一天已完成
-->
Math.max(dp[i-1][1] - prices[i], dp[i-1][2])
dp[i][3] 第 i 天结束时卖出 前一天已完成
-->
Math.max(dp[i-1][2] + prices[i], dp[i-1][3])javascript
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
let [buy1, sell1, buy2, sell2] = [-prices[0], 0, -prices[0], 0];
for (let i = 1; i < prices.length; i++) {
buy1 = Math.max(buy1, - prices[i]);
sell1 = Math.max(buy1 + prices[i], sell1);
buy2 = Math.max(sell1 - prices[i], buy2);
sell2 = Math.max(buy2 + prices[i], sell2);
}
return sell2;
};javascript
买入 k 次 j 代表当前交易完成笔数
j < prices.length >> 1
buy[0][0] -prizes[0]
sell[0][0] 0
buy[i][j] 第 i 天结束持有 之前持有 当天买入
Math.max(buy[i-1][j], sell[i-1][j] - prices[i])
sell[i][j] 第 i 天结束未持有 之前未持有 当天卖出
Math.max(sell[i-1][j], buy[i-1][j-1] + prices[i])javascript
/**
* @param {number} k
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(k, prices) {
if (!prices.length) {
return 0;
}
const len = prices.length;
const max = Math.min(k, len >> 1);
const buy = new Array(len).fill(0).map(item => new Array(max+1).fill(0))
const sell = new Array(len).fill(0).map(item => new Array(max+1).fill(0))
buy[0][0] = -prices[0];
sell[0][0] = 0;
for (let i = 1; i <= max; ++i) {
buy[0][i] = sell[0][i] = Number.MIN_SAFE_INTEGER;
}
for(let i = 1; i < len; i++) {
buy[i][0] = Math.max(buy[i-1][0], sell[i-1][0] - prices[i])
for(let j = 1; j <= max; j ++) {
buy[i][j] = Math.max(buy[i-1][j], sell[i-1][j] - prices[i])
sell[i][j] = Math.max(buy[i-1][j-1] + prices[i], sell[i-1][j])
}
}
return Math.max(...sell[len-1])
};javascript
/**
* @param {number} k
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(k, prices) {
if (!prices.length) {
return 0;
}
const len = prices.length;
const max = Math.min(k, len >> 1);
const buy = new Array(max+1).fill(Number.MIN_SAFE_INTEGER)
const sell = new Array(max+1).fill(Number.MIN_SAFE_INTEGER)
buy[0] = -prices[0];
sell[0] = 0;
for(let i = 1; i < len; i++) {
buy[0] = Math.max(buy[0], sell[0] - prices[i])
for(let j = 1; j <= max; j ++) {
buy[j] = Math.max(buy[j], sell[j] - prices[i])
sell[j] = Math.max(buy[j-1] + prices[i], sell[j])
}
}
return Math.max(...sell)
};