leetcode-122-贪心题-买卖股票的最佳时机II

发表于 | 分类于

题目

1.png

解法

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    // 贪心
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        int profit = 0;
        for(int i = 1; i < prices.size(); ++i){
            int temp = prices[i] - prices[i-1];
            if(temp > 0) profit += temp;
        }

        return profit;
    }

    // 动态规划
    // int maxProfit(vector<int>& prices) {
    //     if(prices.empty()) return 0;
    //     int n = prices.size();
    //     int dp_i_0 = 0, dp_i_1 = -prices[0];
    //     for(int i = 0; i < n; ++i){
    //         int temp = dp_i_0;
    //         dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
    //         dp_i_1 = max(dp_i_1, temp - prices[i]);
    //     }

    //     return dp_i_0;
    // }

    // 动态规划
    // int maxProfit(vector<int>& prices) {
    //     if(prices.empty()) return 0;
    //     int n = prices.size();
    //     vector<vector<int>> dp(n, vector<int>(2));
    //     // int dp[n][2];
    //     for(int i = 0; i < n; ++i){
    //         if(i - 1 == -1){
    //             dp[i][0] = 0;
    //             dp[i][1] = -prices[i];
    //             continue;
    //         }
    //         dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
    //         dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
    //     }

    //     return dp[n-1][0];
    // }
};