Best Time to Buy and Sell Stock I,II,III,VI

Posted on |

Leetcode 121,122,123,188

121.Best Time to Buy and Sell Stock I
和leetcode 53类似，用一个变量来记录子问题的最小值。

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

122.Best Time to Buy and Sell Stock II
贪心，只要这天比前一天高就抛售 lol

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

123.Best Time to Buy and Sell Stock III

DP的解法 two pass

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

188.Best Time to Buy and Sell Stock IV

这个印度小哥讲的不错。
Youtube
状态转移方程
dp[i][j] = max(dp[i][j-1],
for m ~ (0,j) find max( dp[i-1][m] + prices[j] - prices[m])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int len = prices.size();
        if(!len) return 0;
        if (k >= len){
            return quickSolve(prices);
        }
        vector<vector<int>> dp(k+1,vector<int>(len,0));
        for(int i = 1; i <= k; ++i){
            int res = -prices[0];
            for(int j = 1; j < len; ++j){
                 dp[i][j] = max(dp[i][j-1],prices[j] + res);
                 res = max(res, dp[i-1][j] - prices[j]);
            }
        }
        return dp[k][len-1];
    }
    inline int quickSolve(vector<int>& prices){
        int res = 0;
        for(int i = 1; i < prices.size(); ++i){
            res += prices[i] - prices[i-1] > 0 ? prices[i] - prices[i-1] : 0;
        }
        return res;
    }
};

309.Best Time to buy and Sell stock with cooldown