文章目录
  1. 1.
  2. 2. 题解

Best Time to Buy and Sell Stock
Best Time to Buy and Sell Stock III
Best Time to Buy and Sell Stock IV

题解

k=1
当最多只能交易一次时,思路如下:
Say the given array is:
[7, 1, 5, 3, 6, 4]
If we plot the numbers of the given array on a graph, we get:

维护两个变量:minprice代表到目前为止,股票的最低价格;maxprofit代表在最多交易一次的情况下,所能获取的最大利益。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minprice)
minprice = prices[i];
else if (prices[i] - minprice > maxprofit)
maxprofit = prices[i] - minprice;
}
return maxprofit;
}
}

k>1
k=1的情况下比较简单,Best Time to Buy and Sell Stock III是Best Time to Buy and Sell Stock IV的特例,因此,我们研究下k>1的情况即可,找到一个通解。

看完Buy/Sell Stock With K transactions To Maximize Profit Dynamic Programming即可理解此过程。

Best Time to Buy and Sell Stock III leetcode题解给出了详细的解答过程,如下:
DP recursive formula:
dp[k, i] = max(dp[k, i-1], prices[i] - prices[j] + dp[k-1, j-1]), j=[0..i-1]

For k transactions, on i-th day,
if we don’t trade then the profit is same as previous day dp[k, i-1];
and if we bought the share on j-th day where j=[0..i-1], then sell the share on i-th day then the profit is prices[i] - prices[j] + dp[k-1, j-1] .
Actually j can be i as well. When j is i, the one more extra item prices[i] - prices[j] + dp[k-1, j] = dp[k-1, i] looks like we just lose one chance of transaction.

So the straigtforward implementation is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int maxProfit(int K, int[] prices) {
if(K == 0 || prices.length == 0)
return 0;
int dp[][] = new int[K+1][prices.length];
for(int k = 1; k <= K; k++){
for(int i = 1; i < prices.length; i++){
int min = prices[0];
for (int j = 1; j <= i; j++)
min = Math.min(min, prices[j] - dp[k-1][j-1]);
dp[k][i] = Math.max(dp[k][i-1], prices[i] - min);
}
}
return dp[K][prices.length - 1];
}
}

Time complexity is O(kn^2), space complexity is O(kn).

In the above code, min is repeated calculated. It can be easily improved as:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int maxProfit(int K, int[] prices) {
if(K == 0 || prices.length == 0)
return 0;
int dp[][] = new int[K+1][prices.length];
for(int k = 1; k <= K; k++){
int min = prices[0];
for(int i = 1; i < prices.length; i++){
min = Math.min(min, prices[i] - dp[k-1][i-1]);
dp[k][i] = Math.max(dp[k][i-1], prices[i] - min);
}
}
return dp[K][prices.length - 1];
}
}

Time complexity is O(kn), space complexity is O(kn).


如果想获取整个股票交易的过程,可参考StockBuySellKTransactions.java中的代码。

拿张纸,画出动态规划的过程,即可深刻理解该题。


参考资料:

  1. leetcode121题解
  2. Buy/Sell Stock With K transactions To Maximize Profit Dynamic Programming
  3. StockBuySellKTransactions.java
  4. Best Time to Buy and Sell Stock III leetcode题解
文章目录
  1. 1.
  2. 2. 题解