代码随想录算法训练营第36期DAY51

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. };