LeetCode 122 Best Time to Buy and Sell Stock II
题目分析
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
此时对买卖股票的次数不再有限制。
动态规划法
分析：
- 状态：天数，持有状态；
- 动作：买入，卖出，不动；
- base case：第 0 天时不能持有股票，此时利润为 0（实现中可以搞成如果持有的话，利润为 INT_MIN）。
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size() + 1, vector<int>(2, 0));
dp[0][1] = INT_MIN;
for (int d = 1; d <= prices.size(); d++) {
dp[d][0] = max(dp[d-1][0], dp[d-1][1] + prices[d - 1]);
dp[d][1] = max(dp[d-1][1], dp[d-1][0] - prices[d - 1]);
}
return dp[prices.size()][0];
}
};
直接法
这是我 2020 年做的时候的解法，当时用的 Java。
实际上分析题目后我们可以当价格有上升就立刻卖出，或者这样想， 我们每天都买入卖出，其中有些赔有些赚，剔除掉其中赔钱的即可。
class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
int lastPrice = Integer.MAX_VALUE;
for(int price: prices){
if(price > lastPrice){
profit += price - lastPrice;
}
lastPrice = price;
}
return profit;
}
}