LeetCode - Best Time to Buy and Sell Stock IV
Problem description
Say you have an array for which the i-th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
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
2
3
Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
1
2
3
4
Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Analysis
Basically we can use DP and state machine to solve this. Just one thing to remember, you need to first check if the k is bigger enough so that we can buy and sell unlimited times.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public int maxProfit(int k, int[] prices) {
if (k == 0){
return 0;
}
int days = prices.length;
if(k >= days / 2) {
int maxProfit = 0;
for(int i = 1; i < days; i++)
if(prices[i] > prices[i - 1])
maxProfit += prices[i] - prices[i - 1];
return maxProfit;
}
int[] buy = new int[k];
int[] sell = new int[k];
Arrays.fill(buy, Integer.MIN_VALUE);
for (int i = 0;i<prices.length; i++){
int cost = prices[i];
for (int j = 0; j < k;j++){
if (j == 0){
buy[j] = Math.max(buy[j], -cost);
}
else{
buy[j] = Math.max(buy[j], sell[j-1]-cost);
}
sell[j] = Math.max(sell[j], buy[j] + cost);
}
}
return sell[k-1];
}
}