买卖股票总结
Stocking #
dp for stocking I #
To solve this, calculate profit until we find a smaller stock.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
min_price = prices[0]
max_profit = 0
for i in range(1, len(prices)):
if prices[i] < min_price:
min_price = prices[i]
else:
max_profit = max(max_profit, prices[i] - min_price)
return max_profit
dp for stocking II #
Use greedy approach. Initialize a profit to be 0. loop through the prices array, if the current price is larger than the previous one, add the difference to the profit.
This method works because for the case that stock continues to climb up for several days, we add up the profit for each day. And it sum up to the same as the difference between the last day and the first day.
The total profit can be expressed as the sum of the differences of prices on subsequent days:
$$ \text{profit} = \sum_{i=1}^{n} (p_i - p_{i-1}) $$
Expanding the summation gives:
$$ \text{profit} = p_n - p_{n-1} + p_{n-1} - p_{n-2} + … + p_1 - p_0 $$
Now, notice that each price ( p_i ) for ( i ) from 1 to ( n-1 ) appears twice, once as a positive term and once as a negative term, and they cancel each other out. Hence, we get:
$$ \text{profit} = p_n - p_0 $$
class Solution {
public:
int maxProfit(vector<int>& prices) {
int profit = 0;
for (int i = 1; i < prices.size(); i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
};
dp for stocking III #
Subproblem for stocking IV with k = 2.
dp for stocking IV #
Problem is to find the maximum profit with at most k transactions.
we can keep track of two states for each day: the maximum profit with stock in hand and the maximum profit without stock in hand.index i represents the i-th day.
$$ \begin{aligned} maxProfitWithStock[j][i] &= \max(maxProfitWithStock[j][i-1], maxProfit[j-1][i-1] - prices[i]) \ maxProfit[j][i] &= \max(maxProfit[j][i-1], maxProfitWithStock[j][i] + prices[i]) \end{aligned} $$
We can view more in depth for each part of these equation.
$$ \begin{aligned} maxProfitWithStock[j][i] &= \max(maxProfitWithStock[j][i-1], maxProfit[j-1][i-1] - prices[i]) \ \end{aligned} $$
- maxProfitWithStock[j][i-1] means we do not sell the stock at day i.
- maxProfitWithStock[j-1][i-1] - prices[i] means we buy the stock at day i with the max profit of j-1 transactions at day i-1(maxProfit[j-1][i-1]).
$$ \begin{aligned} maxProfit[j][i] &= \max(maxProfit[j][i-1], maxProfitWithStock[j][i] + prices[i]) \end{aligned} $$
- maxProfit[j][i-1] means we can make more money if we don’t sell the stock on day i.
- maxProfitWithStock[j][i] + prices[i] means we sell the stock on day i.
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
vector<vector<int>> maxProfitWithStock(k + 1, vector<int>(n, 0));
vector<vector<int>> maxProfit(k + 1, vector<int>(n, 0));
for (int j = 1; j <= k; j++) {
maxProfitWithStock[j][0] = -prices[0];
for (int i = 1; i < n; i++) {
maxProfitWithStock[j][i] = max(maxProfitWithStock[j][i - 1], maxProfit[j - 1][i - 1] - prices[i]);
maxProfit[j][i] = max(maxProfit[j][i - 1], maxProfitWithStock[j][i] + prices[i]);
}
}
return maxProfit[k][n - 1];
}
};
Optimization #
We can see that the maxProfitWithStock[j][i] only depends on the previous day. So we can use a integer to store it.
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
vector<vector<int>> maxProfit(k + 1, vector<int>(n, 0));
for (int j = 1; j <= k; j++) {
int maxProfitWithStock = -prices[0];
for (int i = 1; i < n; i++) {
maxProfitWithStock = max( maxProfitWithStock, maxProfit[j-1][i-1]-prices[i]);
maxProfit[j][i] = max(maxProfit[j][i - 1], maxProfitWithStock + prices[i]);
}
}
return maxProfit[k][n - 1];
}
};
then We can see that the maxProfit[j][i] only depends on the previous row. So we can use a vector to store it.
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
vector<int> maxProfit(n,0);
for (int j = 1; j <= k; j++) {
auto tmp = maxProfit;
int maxProfitWithStock = -prices[0];
for (int i = 1; i < n; i++) {
maxProfitWithStock = max( maxProfitWithStock, tmp[i-1]-prices[i]);
maxProfit[i] = max(maxProfit[i - 1], maxProfitWithStock + prices[i]);
}
}
return maxProfit[n - 1];
}
};
Now we can see that the tmp Only depends on the previous element. So we can use a integer to store it.
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
vector<int> maxProfit(n,0);
for (int j = 1; j <= k; j++) {
auto tmp = maxProfit[0];
int maxProfitWithStock = -prices[0];
for (int i = 1; i < n; i++) {
maxProfitWithStock = max( maxProfitWithStock, tmp-prices[i]);
tmp =maxProfit[i];
maxProfit[i] = max(maxProfit[i - 1], maxProfitWithStock + prices[i]);
}
}
return maxProfit[n - 1];
}
};
| Original Code | Optimized Code |
|---|---|
|
|