|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
3 | | -/** |
4 | | -
|
5 | | - 188. Best Time to Buy and Sell Stock IV |
6 | | -
|
7 | | - Say you have an array for which the ith element is the price of a given stock on day i. |
8 | | -
|
9 | | - Design an algorithm to find the maximum profit. You may complete at most k transactions. |
10 | | -
|
11 | | - Note: |
12 | | - You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). |
13 | | -
|
14 | | - Example 1: |
15 | | - Input: [2,4,1], k = 2 |
16 | | - Output: 2 |
17 | | - Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2. |
18 | | -
|
19 | | - Example 2: |
20 | | - Input: [3,2,6,5,0,3], k = 2 |
21 | | - Output: 7 |
22 | | - Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. |
23 | | - Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. |
24 | | -
|
25 | | - */ |
26 | 3 | publicclass_188 { |
27 | | -publicstaticclassSolution1 { |
28 | | -/** credit: https://discuss.leetcode.com/topic/8984/a-concise-dp-solution-in-java */ |
29 | | -publicintmaxProfit(intk,int[]prices) { |
30 | | -intlen =prices.length; |
31 | | -if (k >=len /2) { |
32 | | -returnquickSolve(prices); |
33 | | - } |
34 | | - |
35 | | -int[][]t =newint[k +1][len]; |
36 | | -for (inti =1;i <=k;i++) { |
37 | | -inttmpMax = -prices[0]; |
38 | | -for (intj =1;j <len;j++) { |
39 | | -t[i][j] =Math.max(t[i][j -1],prices[j] +tmpMax); |
40 | | -tmpMax =Math.max(tmpMax,t[i -1][j -1] -prices[j]); |
| 4 | +publicstaticclassSolution1 { |
| 5 | +/** |
| 6 | + * credit: https://discuss.leetcode.com/topic/8984/a-concise-dp-solution-in-java |
| 7 | + */ |
| 8 | +publicintmaxProfit(intk,int[]prices) { |
| 9 | +intlen =prices.length; |
| 10 | +if (k >=len /2) { |
| 11 | +returnquickSolve(prices); |
| 12 | + } |
| 13 | + |
| 14 | +int[][]t =newint[k +1][len]; |
| 15 | +for (inti =1;i <=k;i++) { |
| 16 | +inttmpMax = -prices[0]; |
| 17 | +for (intj =1;j <len;j++) { |
| 18 | +t[i][j] =Math.max(t[i][j -1],prices[j] +tmpMax); |
| 19 | +tmpMax =Math.max(tmpMax,t[i -1][j -1] -prices[j]); |
| 20 | + } |
| 21 | + } |
| 22 | +returnt[k][len -1]; |
41 | 23 | } |
42 | | - } |
43 | | -returnt[k][len -1]; |
44 | | - } |
45 | 24 |
|
46 | | -privateintquickSolve(int[]prices) { |
47 | | -intlen =prices.length; |
48 | | -intprofit =0; |
49 | | -for (inti =1;i <len;i++) { |
50 | | -// as long as there is a price gap, we gain a profit. |
51 | | -if (prices[i] >prices[i -1]) { |
52 | | -profit +=prices[i] -prices[i -1]; |
| 25 | +privateintquickSolve(int[]prices) { |
| 26 | +intlen =prices.length; |
| 27 | +intprofit =0; |
| 28 | +for (inti =1;i <len;i++) { |
| 29 | +// as long as there is a price gap, we gain a profit. |
| 30 | +if (prices[i] >prices[i -1]) { |
| 31 | +profit +=prices[i] -prices[i -1]; |
| 32 | + } |
| 33 | + } |
| 34 | +returnprofit; |
53 | 35 | } |
54 | | - } |
55 | | -returnprofit; |
56 | 36 | } |
57 | | - } |
58 | 37 | } |