提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 一、121. 买卖股票的最佳时机
- 二、122.买卖股票的最佳时机II
一、121. 买卖股票的最佳时机
class Solution {
public:
int maxProfit(vector<int>& prices) {
int profit = 0;
int buyPrice = prices[0];
vector<int> dp(prices.size(), 0);
for (int i = 1; i < prices.size(); i ++) {
dp[i] = max(dp[i-1], prices[i] - buyPrice);
buyPrice = min(buyPrice, prices[i]);
}
return dp.back();
}
};
二、122.买卖股票的最佳时机II
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<int> dp(prices.size(), 0);
int buyPrice = prices[0];
for (int i = 1; i < prices.size(); i ++) {
dp[i] = dp[i-1];
if (prices[i] > buyPrice) {
dp[i] += prices[i] - buyPrice;
}
buyPrice = prices[i];
}
return dp.back();
}
};
标准dp写法:
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<int> dp(2, 0);
dp[0] = - prices[0];
for (int i = 1; i < prices.size(); i ++) {
dp[0] = max(dp[1] - prices[i], dp[0]);
dp[1] = max(dp[1], dp[0] + prices[i]);
}
return dp[1];
}
};