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

面试经典150题 day8

- - 题目来源
  - 我的题解
  - - 方法一动态规划
    - 方法二贪心+一次遍历

题目来源

力扣每日一题；题序：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],\ldots,(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])+\ldots+(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 的区间即能使得答案最大化，因此最后答案为 $\textit{ans}=\sum_{i=1}^{n-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;
}