|
| 1 | +packagehard; |
| 2 | + |
| 3 | + |
| 4 | +/**123. Best Time to Buy and Sell Stock III QuestionEditorial Solution My Submissions |
| 5 | +Total Accepted: 62880 |
| 6 | +Total Submissions: 231914 |
| 7 | +Difficulty: Hard |
| 8 | +Say you have an array for which the ith element is the price of a given stock on day i. |
| 9 | +
|
| 10 | +Design an algorithm to find the maximum profit. You may complete at most two transactions. |
| 11 | +
|
| 12 | +Note: |
| 13 | +You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).*/ |
| 14 | +publicclassBestTimeToBuyAndSellStockIII { |
| 15 | + |
| 16 | +//this is a very clear solution and very highly upvoted in Discuss, but not extensibel to K solution. |
| 17 | +publicintmaxProfit(int[]prices) { |
| 18 | +if(prices.length <2)return0; |
| 19 | +intbuy1 =Integer.MIN_VALUE,buy2 =Integer.MIN_VALUE;//we use negative numbers to denote buy1 and buy2, thus use Integer.MIN_VALUE here is more convenient. |
| 20 | +intsell1 =0,sell2 =0; |
| 21 | +for(inti =0;i <prices.length;i++){ |
| 22 | +buy1 =Math.max(buy1, -prices[i]); |
| 23 | +sell1 =Math.max(sell1,buy1+prices[i]); |
| 24 | +buy2 =Math.max(buy2,sell1-prices[i]); |
| 25 | +sell2 =Math.max(sell2,buy2+prices[i]); |
| 26 | + } |
| 27 | +returnsell2; |
| 28 | + } |
| 29 | + |
| 30 | +//this one could make it AC'ed on OJ, but when I use this one to BestTimeToBuyAndSellStockIV, it got Memory Limit Exceeded. |
| 31 | +//this one is optimized from maxProfit_optimized() below |
| 32 | +publicintmaxProfit_optimized(int[]prices) { |
| 33 | +if(prices.length <2)return0; |
| 34 | +intK =2; |
| 35 | +int[][]dp =newint[K+1][prices.length]; |
| 36 | +for(inti =1;i <=K;i++){ |
| 37 | +intmaxDiff = -prices[0]; |
| 38 | +for(intj =1;j <prices.length;j++){ |
| 39 | +dp[i][j] =Math.max(dp[i][j-1],prices[j] +maxDiff); |
| 40 | +maxDiff =Math.max(maxDiff,dp[i-1][j] -prices[j]); |
| 41 | + } |
| 42 | + } |
| 43 | +returndp[K][prices.length-1]; |
| 44 | + } |
| 45 | + |
| 46 | +// |
| 47 | +publicintmaxProfit_TLE(int[]prices) { |
| 48 | +/** |
| 49 | + * Thanks to this post: https://discuss.leetcode.com/topic/4766/a-clean-dp-solution-which-generalizes-to-k-transactions/29 |
| 50 | + * and Tushar's video:https://www.youtube.com/watch?v=oDhu5uGq_ic&feature=youtu.be |
| 51 | + * |
| 52 | + * use this dp strategy: |
| 53 | + * |
| 54 | + * dp[i][j] = Math.max(dp[i][j-1], (prices[i] - prices[m]) + dp[i-1][m]) with m in (0, j-1) |
| 55 | + * row is price |
| 56 | + * column is day |
| 57 | + * dp[i][j] means the max profit you can make on day j by doing a max of i transactions. |
| 58 | + * |
| 59 | + * dp[i][j-1] |
| 60 | + * means no transaction on day j, so the max profit you could get is on the previous day j-1 |
| 61 | + * |
| 62 | + * (prices[i] - prices[m]) + dp[i-1][m] |
| 63 | + * (prices[i] - prices[m]) means you'll sell on day j, this means you'll do one transaction on day j with sell price: prices[m], |
| 64 | + * and the buy price could be any price that is on the day prior to day j, we call it day m, thus m is |
| 65 | + * in this range: (0, j-1) |
| 66 | + * dp[i-1][m] means you'll have i-1 transaction to do on day m to make up to i transactions, since you do one transaction on day j, that's why |
| 67 | + * we deduct 1 from i |
| 68 | + * |
| 69 | + * */ |
| 70 | +if(prices.length <2)return0; |
| 71 | +else { |
| 72 | +/**First row should be zero because it means, you're allowed to make ZERO transaction, so no profit |
| 73 | + * First column should be zero because it means, on day ZERO, you could only buy and make no profit*/ |
| 74 | +intK =2;//number of allowed transactions. |
| 75 | +intdp[][] =newint[K+1][prices.length]; |
| 76 | +for(inti =1;i <=K;i++){ |
| 77 | +for(intj =1;j <prices.length;j++){ |
| 78 | +intmaxProfitOnDayJ =0; |
| 79 | +for(intm =0;m <j;m++){ |
| 80 | +maxProfitOnDayJ =Math.max(maxProfitOnDayJ,prices[j] -prices[m] +dp[i-1][m]); |
| 81 | + } |
| 82 | +dp[i][j] =Math.max(dp[i][j-1],maxProfitOnDayJ); |
| 83 | + } |
| 84 | + } |
| 85 | +returndp[K][prices.length-1]; |
| 86 | + } |
| 87 | + } |
| 88 | + |
| 89 | +publicstaticvoidmain(String...strings){ |
| 90 | +// int[] prices = new int[]{6,1,3,2,4,7}; |
| 91 | +// int[] prices = new int[]{1,2,4,2,5,7,2,4,9,0};//(7-2)+(9-2) = 5+7 = 12 is wrong, it should be (7-1)+(9-2) = 6+7 = 13 |
| 92 | +int[]prices =newint[]{2,5,7,1,4,3,1,3}; |
| 93 | +BestTimeToBuyAndSellStockIIItest =newBestTimeToBuyAndSellStockIII(); |
| 94 | +System.out.println(test.maxProfit(prices)); |
| 95 | + } |
| 96 | + |
| 97 | +/**I try to find the regional max price, then compute the profit, but failed at this test case: |
| 98 | + * 1,2,4,2,5,7,2,4,9,0*/ |
| 99 | +publicintmaxProfit_2nd_attempt(int[]prices) { |
| 100 | +int[]profits =newint[2]; |
| 101 | +booleanflip =false; |
| 102 | +for(inti =1;i <prices.length;i++){ |
| 103 | +intbuyPrice =prices[i-1]; |
| 104 | +if(prices[i] >prices[i-1])flip =true; |
| 105 | +while(i <prices.length &&prices[i] >prices[i-1])i++; |
| 106 | +if(flip)i--; |
| 107 | +intprofit =prices[i] -buyPrice; |
| 108 | +//update the smaller profit in profits array |
| 109 | +intsmallerIndex =profits[0] <profits[1] ?0 :1; |
| 110 | +profits[smallerIndex] =Math.max(profits[smallerIndex],profit); |
| 111 | +flip =false;; |
| 112 | + } |
| 113 | +returnprofits[0] +profits[1]; |
| 114 | + } |
| 115 | + |
| 116 | +/**Greedy approach won't work like Best Time to Buy and Sell Stock II because: |
| 117 | + * 1. we need to track a regional min buy price instead of just the previous one; |
| 118 | + * 2. we're allowed to do only TWO transactions. |
| 119 | + * e.g test case: 6,1,3,2,4,7*/ |
| 120 | +publicintmaxProfit_1st_attempt(int[]prices) { |
| 121 | +int[]profits =newint[2]; |
| 122 | +for(inti =1;i <prices.length;i++){ |
| 123 | +if(prices[i] >prices[i-1]){ |
| 124 | +intsmallerIndex =profits[0] >profits[1] ?1 :0; |
| 125 | +profits[smallerIndex] =Math.max(prices[i] -prices[i-1],profits[smallerIndex]); |
| 126 | + } |
| 127 | + } |
| 128 | +returnprofits[0] +profits[1]; |
| 129 | + } |
| 130 | +} |