面试经典150题 买卖股票的最佳时机 II

题目来源

力扣每日一题；题序：122

我的题解

方法一 动态规划

与 买卖股票的最佳时机 的区别在于：可以多次买入、卖出。

时间复杂度：O(n)
空间复杂度：O(n)

public int maxProfit(int[] prices) {
    int n=prices.length;
    int[][] dp=new int[n][2];//0买 1卖
    for(int i=0;i<n;i++){
        if(i==0){
            dp[i][0]=-prices[0];
            dp[i][1]=0;
            continue;
        }
        dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
        dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
    }
    return dp[n-1][1];
}

//空间优化版本
public int maxProfit(int[] prices) {
    int n=prices.length;
    int dp_0=-prices[0];//买
    int dp_1=0;//卖
    for(int i=1;i<n;i++){
        int t=dp_0;
        dp_0=Math.max(dp_0,dp_1-prices[i]);
        dp_1=Math.max(dp_1,t+prices[i]);
    }
    return dp_1;
}

方法二 贪心+一次遍历

由于股票的购买没有限制，因此整个问题等价于寻找 x 个不相交的区间$(l_i,r_i]$使得如下的等式最大化${\sum }_{i=1}^{x}a[r_i]-a[l_i]i=1$,其中 $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],\dots ,(r_i-1,r_i]$这若干个区间长度为 1 的区间的价值和，即
$a[r_i]-a[l_i]=(a[r_i]-a[r_i-1])+(a[r_i-1]-a[r_i-2])+\dots +(a[l_i+1]-a[l_i])$
因此问题可以简化为找 x 个长度为 1 的区间 $(l_i,l_i+1]$使得 ${\sum }_{i=1}^{x}a[l_i+1]-a[l_i]$价值最大化。
贪心的角度考虑每次选择贡献大于 0 的区间即能使得答案最大化，因此最后答案为 ans = ∑ i = 1 n − 1 max ⁡ { 0 , a [ i ] − a [ i − 1 ] } \textit{ans}=\sum_{i=1}^{n-1}\max\{0,a[i]-a[i-1]\} ans=∑i=1n−1​max{0,a[i]−a[i−1]},其中 n 为数组的长度。
贪心算法只能用于计算最大利润，计算的过程并不是实际的交易过程。

时间复杂度：O(n)
空间复杂度：O(1)

public int maxProfit(int[] prices) {
    int total=0;
    int len=prices.length;
    for(int i=1;i<len;i++){
        if(prices[i]>prices[i-1]){
            total+=prices[i]-prices[i-1];
        }
    }
    return total;
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~

原文地址：https://blog.csdn.net/weixin_42075274/article/details/137830412

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！