题目链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

题目描述:

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

解法1

依次找到每个区间的最小值和最大值,然后相加得到最大收益

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var maxProfit = function(prices) {
let i = 0;
let len = prices.length;
let res = 0;
while(i < len - 1) {
let min = 0;
let max = 0;
while(i < len - 1 && prices[i] >= prices[i+1]) {
i++; // 找最小值
}
min = prices[i]; // 找到了当前区间的最小值
while(i < len - 1 && prices[i] <= prices[i+1]) {
i++; // 找最大值
}
max = prices[i]; // 找到了当前区间的最大值
res += (max - min);
}

return res;
};

解法2

使用贪心算法,所有的连续上升区间都加上,最后得到一个最优解

1
2
3
4
5
6
7
8
9
10
11

var maxProfit = function(prices) {
let len = prices.length;
let res = 0;
for (let i = 1; i < len; i++ ){
if (prices[i] > prices[i - 1]) {
res += prices[i] - prices[i - 1];
}
}
return res;
};

解法3

动态规划的一个解法。定义状态方程dp[i][j], 其中i代表当前第几天,j代表当前是卖出还是买入,卖出为0, 买入为1。

因此最后的结果就是dp[len-1][0], 因为最后一天肯定是卖出的。

第 i 天的卖出买入分别的收入:

dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]) 第 i 天卖出股票的最大收益 等于 第 i-1 天卖出股票的收入或者第 i-1 天买入股票加上第 i 天卖出的股票的钱 这两种情况下的最大值。

dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]); 第 i 天买入股票的最大收益等于 第 i-1 天买入股票的收益或者第 i-1 天卖出股票减去第 i 天买股票花的钱,这两种情况下的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var maxProfit = function(prices) {
let dp = [];
let len = prices.length;
prices.forEach((item,index) => dp[index] = []);

dp[0][0] = 0; // 第一天不买的话收益为0
dp[0][1] = -prices[0]; // 第一天买入股票的话,收益为负

for(let i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
}

return dp[len - 1][0];
};

总结

上述三种解法均是一次遍历便能搞定,因此时间复杂度是 O(N), 空间复杂度为O(1)。