[数据结构与算法]122 买卖股票的最佳时机-02

122 买卖股票的最佳时机-02

动态规划

class Solution {
    public int maxProfit(int[] prices) {
        
        int dp_0 = 0;
        int dp_1 = -prices[0];

        for(int i=1;i<prices.length;i++){
           int tmp_dp_0 = Math.max(dp_0,dp_1+prices[i]);
           int tmp_dp_1 = Math.max(dp_1,dp_0-prices[i]);
           dp_0 = tmp_dp_0;
           dp_1 = tmp_dp_1;
        }
        return dp_0;
    }
}

时间复杂度$O(n)$，其中$n$是$prices$数组的长度。
空间复杂度$O(1)$。

贪心

由于股票的购买没有限制，因此整个问题等价于寻找$x$个不想交的区间$(l_i,r_i]$使得下面的式子最大化$$\sum _{i=1}^{x}a[r_i]?a[l_i]$$
其中$l_i$表示在第$l_i$天买入，$r_i$表示在$r_i$卖出。

我们注意到对于 $(l_i,r_i]$ 这一区间贡献的价值 $a[r_i]?a[l_i]$ ，等价于$(l_i,l_{i+1}],(l_{i+1},l_{i+2}],...,(r_{i?1},r_i]$ 这若干个区间长度为$1$的价值和。

贪心的角度考虑，我们每次选择贡献大于$0$的区间就能使答案最大化。

需要说明的是，贪心算法只能用于计算最大利润，计算过程并不是实际的交易过程。

class Solution {
    public int maxProfit(int[] prices) {
        
        int max_profit = 0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]-prices[i-1]>0){
                max_profit+=prices[i]-prices[i-1];
            }
        }

        return max_profit;
    }
}

时间复杂度$O(n)$，其中$n$是$prices$数组的长度。
空间复杂度$O(1)$。