Leetcode
Dynamic Programming
188 Best Time to Buy and Sell Stock IV

1. Question

Say you have an array for which theithelement is the price of a given stock on dayi.
Design an algorithm to find the maximum profit. You may complete at mostktransactions.
Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Example 1:
1
Input: [2,4,1], k = 2
2
3
Output: 2
4
5
Explanation:
6
Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Copied!
Example 2:
1
Input: [3,2,6,5,0,3], k = 2
2
3
Output: 7
4
5
Explanation:
6
Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
7
Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Copied!

2. Implementation

(1) DP
1
class Solution {
2
public int maxProfit(int k, int[] prices) {
3
if (prices == null || prices.length == 0) {
4
return 0;
5
}
6
7
if (k >= prices.length / 2) {
8
return maxProfitWithUnlimitedTransactions(prices);
9
}
10
11
int[][] dp = new int[k + 1][prices.length];
12
13
for (int i = 1; i <= k; i++) {
14
int holding = -prices[0];
15
for (int j = 1; j < prices.length; j++) {
16
dp[i][j] = Math.max(dp[i][j - 1], holding + prices[j]);
17
holding = Math.max(holding, dp[i - 1][j - 1] - prices[j]);
18
}
19
}
20
return dp[k][prices.length - 1];
21
}
22
23
public int maxProfitWithUnlimitedTransactions(int[] prices) {
24
int curMax = 0;
25
int max = 0;
26
27
for (int i = 1; i < prices.length; i++) {
28
curMax = prices[i] > prices[i - 1] ? curMax + prices[i] - prices[i - 1] : curMax;
29
max = Math.max(max, curMax);
30
}
31
return max;
32
}
33
}
Copied!

3. Time & Space Complexity

DP: 时间复杂度O(nk), 空间复杂度O(nk)