DAY51

121買賣股票的最佳時機

做過了。算是二刷：來自力扣優質題解

貪心：

每次記錄更新最小點和最大出售值。

1. class?Solution?{
2. public:
3. ????int?maxProfit(vector<int>&?prices)?{
4. ????????int?cur,res=INT_MIN,curmin=INT_MAX;
5. ????????for(int?i=0;i<prices.size();i++){
6. ????????????if(prices[i]<curmin)?curmin=prices[i];
7. ????????????cur=prices[i]-curmin;
8. ????????????if(cur>res)?res=cur;
9. ????????}
10. ????????return?res;
11. ????}
12. };

暴力：

1. class?Solution?{
2. public:
3. ????int?maxProfit(vector<int>&?prices)?{
4. ????????int?res=0;
5. ????????for(int?i=0;i<prices.size();i++){
6. ????????????for(int?j=i+1;j<prices.size();j++)
7. ????????????res=max(res,prices[j]-prices[i]);
8. ????????}
9. ????????return?res;
10. ????}
11. };

動態規劃：

算是比較系統的東西，記在紙質筆記本吧。

1. class?Solution?{
2. public:
3. ????int?maxProfit(vector<int>&?prices)?{
4. ????????if(prices.size()==1)?return?0;
5. ????????vector<vector<int>>?dp(prices.size(),vector<int>(2));
6. ????????dp[0][0]=-1*prices[0];
7. ????????dp[0][1]=0;
8. ????????for(int?i=1;i<prices.size();i++){
9. ????????????dp[i][0]=max(-prices[i],dp[i-1][0]);
10. ????????????dp[i][1]=max(prices[i]+dp[i-1][0],dp[i-1][1]);
11. ????????}
12. ????????return?dp[prices.size()-1][1];
13. ????}
14. };

滾動數組法：

1. class?Solution?{
2. public:
3. ????int?maxProfit(vector<int>&?prices)?{
4. ????????if(prices.size()==1)?return?0;
5. ????????vector<int>?dp(2);
6. ????????dp[0]=-1*prices[0];
7. ????????dp[1]=0;
8. ????????for(int?i=1;i<prices.size();i++){
9. ????????????dp[0]=max(-prices[i],dp[0]);
10. ????????????dp[1]=max(prices[i]+dp[0],dp[1]);
11. ????????}
12. ????????return?dp[1];
13. ????}
14. };

時間竟然也快了很多，不知道為什么。

122買賣股票的最佳時機ii

做過貪心法：只要能賺錢就買賣。

1. class?Solution?{
2. public:
3. ????int?maxProfit(vector<int>&?prices)?{
4. ????????if(prices.size()==1)?return?0;
5. ????????int?sum=0;
6. ????????for(int?i=1;i<prices.size();i++){
7. ????????????int?res=prices[i]-prices[i-1];
8. ????????????if(res>0)?sum+=res;
9. ????????}
10. ????????return?sum;
11. ????}
12. };

動態規劃：

想對了，[多次買入和一次買入]和上一題不同的地方就是多了一個項：-price[i]不夠了，要寫成：dp[i-1][1]-price[i]

1. class?Solution?{
2. public:
3. ????int?maxProfit(vector<int>&?prices)?{
4. ????????if?(prices.size()?==?1)
5. ????????????return?0;
6. ????????vector<vector<int>>?dp(prices.size(),?vector<int>(2));
7. ????????dp[0][0]?=?-1?*?prices[0];
8. ????????dp[0][1]?=?0;
9. ????????for?(int?i?=?1;?i?<?prices.size();?i++)?{
10. ????????????dp[i][0]?=?max(dp[i?-?1][1]?-?prices[i],?dp[i?-?1][0]);
11. ????????????dp[i][1]?=?max(dp[i?-?1][0]?+?prices[i],?dp[i?-?1][1]);
12. ????????}
13. ????????return?dp[prices.size()?-?1][1];
14. ????}
15. };

滾動數組：

1. class?Solution?{
2. public:
3. ????int?maxProfit(vector<int>&?prices)?{
4. ????????if?(prices.size()?==?1)
5. ????????????return?0;
6. ????????vector<int>?dp(2);
7. ????????dp[0]?=?-1?*?prices[0];
8. ????????dp[1]?=?0;
9. ????????for?(int?i?=?1;?i?<?prices.size();?i++)?{
10. ????????????dp[0]?=?max(dp[1]?-?prices[i],?dp[0]);
11. ????????????dp[1]?=?max(dp[0]?+?prices[i],?dp[1]);
12. ????????}
13. ????????return?dp[1];
14. ????}
15. };