LeetCode122 买卖股票的最佳时机II

链接: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
给定一个数组 prices ,其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

这一题贪心和dp两种解法都可以做。
首先是贪心,只要当前的价格低于之前出现的高价,就在之前的高价处卖出,并在当天买入。
贪心做法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<int> dp(prices.size());
int now = prices[0], total = 0, pre = prices[0];
for(int i = 1; i < prices.size(); i++) {
if (prices[i] < now) {
total += now - pre;
now = pre = prices[i];
}
else {
now = prices[i];
if (i == prices.size() - 1) {
total += now - pre;
}
}
}
return total;
}
};

动态规划做法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size());
for(auto &idx: dp) {
idx.resize(2);
}
dp[0][1] = -prices[0];
// dp[i][0]表示第i天无股票的最大利润 dp[i][1]表示第i天持有股票的最大利润
for(int i = 1; i < prices.size(); i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[prices.size() - 1][0];
}
};