题目来源

力扣每日一题；题序：122

我的题解

方法一 动态规划

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

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

java">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];
}

java">//空间优化版本
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)

java">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;
}

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