mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
46 lines
1.5 KiB
Markdown
46 lines
1.5 KiB
Markdown
# [122. Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/)
|
||
|
||
update: LeetCode六道股票买卖题目总结见我的博客文章[动态规划之股票买卖系列](https://shusentang.github.io/2019/11/03/Buy-and-Sell-Stock/)
|
||
|
||
# 思路
|
||
## 比较好想的思路
|
||
如果分别知道了前0到前i天的最大利润dp[0...i]，那么前i+1天的最大利润就为：
|
||
max(dp[j] + max(prices[i+1] - prices[k])), 其中k属于j~i+1
|
||
以上思路时间复杂度为O(n^2), 空间复杂度为O(n)
|
||
## 改进
|
||
运用贪心的思想：只要有利润(即prices[i] > prices[i-1])就可以买入卖出, 即不错过任何利润。
|
||
此时时间复杂度O(n), 空间复杂度为O(1)
|
||
|
||
# C++
|
||
改进前：
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int maxProfit(vector<int>& prices) {
|
||
if(prices.size() == 0) return 0;
|
||
int dp[prices.size()] = {0};
|
||
int min_price;
|
||
for(int i = 1; i < prices.size(); i++){
|
||
min_price = prices[i];
|
||
for(int j = i-1; j >= 0; j--){
|
||
if(min_price > prices[j]) min_price = prices[j];
|
||
if(dp[j] + prices[i] - min_price > dp[i]) dp[i] = dp[j] + prices[i] - min_price;
|
||
}
|
||
}
|
||
return dp[prices.size() - 1];
|
||
}
|
||
};
|
||
```
|
||
改进后：
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int maxProfit(vector<int>& prices) {
|
||
int max_profit = 0;
|
||
for(int i = 1; i < prices.size(); i++)
|
||
if(prices[i] > prices[i-1]) max_profit += (prices[i] - prices[i-1]);
|
||
return max_profit;
|
||
}
|
||
};
|
||
```
|