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
| class Solution {
public int maxProfit(int k, int[] prices) {
if (prices == null || prices.length <= 1) return 0;
if (2 * k > prices.length) {
int ans = 0;
for (int i = 1; i < prices.length; i++) {
ans += Math.max(prices[i] - prices[i - 1], 0);
}
return ans;
}
int[][] dp = new int[2][2 * k + 1];
for (int i = 0; i < 2 * k + 1; i++) {
dp[0][i] = 0;
}
for (int i = 1; i < prices.length; i++) {
for (int j = 0; j <= 2 * k; j += 2) {
dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j], j - 1 >= 0? dp[(i - 1) % 2][j - 1] + prices[i] - prices[i - 1] : 0);
}
for (int j = 1; j <= 2 * k -1; j += 2) {
int profit = prices[i] - prices[i - 1];
dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j] + profit, dp[(i - 1) % 2][j - 1]);
if (j >= 2) {
dp[i % 2][j] = Math.max(dp[i % 2][j], dp[(i - 1) % 2][j - 2] + profit);
}
}
}
int r = (prices.length - 1) % 2;
int ans = 0;
for (int i = 0; i < 2 * k + 1; i++) {
ans = Math.max(ans, dp[r][i]);
}
return ans;
}
}
|