|
| 1 | +packageeasy; |
| 2 | + |
| 3 | +/**121. Best Time to Buy and Sell Stock QuestionEditorial Solution My Submissions |
| 4 | +Total Accepted: 117685 |
| 5 | +Total Submissions: 318311 |
| 6 | +Difficulty: Easy |
| 7 | +Say you have an array for which the ith element is the price of a given stock on day i. |
| 8 | +
|
| 9 | +If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit. |
| 10 | +
|
| 11 | +Example 1: |
| 12 | +Input: [7, 1, 5, 3, 6, 4] |
| 13 | +Output: 5 |
| 14 | +
|
| 15 | +max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price) |
| 16 | +Example 2: |
| 17 | +Input: [7, 6, 4, 3, 1] |
| 18 | +Output: 0 |
| 19 | +
|
| 20 | +In this case, no transaction is done, i.e. max profit = 0.*/ |
| 21 | +publicclassBestTimeToBuyAndSellStock { |
| 22 | +/**The key here is that you'll have to buy first, before you can sell. |
| 23 | + * That means, if the lower price comes after a higher price, their combination won't work! Since you cannot sell first |
| 24 | + * before you buy it.*/ |
| 25 | +publicintmaxProfit(int[]prices) { |
| 26 | +//use current price to deduct the previous min to get current profit, and then take the max from previousMax and this newly calculated max |
| 27 | +if(prices ==null ||prices.length <2)return0; |
| 28 | +intmin =prices[0],prevProf =0,currPro =0; |
| 29 | +for(inti =1;i <prices.length;i++){ |
| 30 | +currPro =Math.max(prices[i] -min,prevProf); |
| 31 | +min =Math.min(min,prices[i]); |
| 32 | +prevProf =currPro; |
| 33 | + } |
| 34 | +returncurrPro; |
| 35 | + } |
| 36 | + |
| 37 | +publicstaticvoidmain(String...strings){ |
| 38 | +// int[] prices = new int[]{7,1,5,3,6,4}; |
| 39 | +// int[] prices = new int[]{7,6,4,3,1}; |
| 40 | +// int[] prices = new int[]{2,4,1}; |
| 41 | +int[]prices =newint[]{1,2}; |
| 42 | +BestTimeToBuyAndSellStocktest =newBestTimeToBuyAndSellStock(); |
| 43 | +System.out.println(test.maxProfit(prices)); |
| 44 | + } |
| 45 | + |
| 46 | +publicintmaxProfit_attemp1(int[]prices) { |
| 47 | +if(prices ==null ||prices.length <2)return0; |
| 48 | +intminBuy =prices[0],maxSell =prices[1],maxProfit =0; |
| 49 | +for(inti =1;i <prices.length;i++){ |
| 50 | +if(maxSell >minBuy){ |
| 51 | +maxProfit =Math.max(maxProfit,maxSell-minBuy); |
| 52 | + } |
| 53 | +if(prices[i] <minBuy){ |
| 54 | +minBuy =prices[i]; |
| 55 | + } |
| 56 | +if(prices[i] >maxSell){ |
| 57 | +maxSell =prices[i]; |
| 58 | + } |
| 59 | + } |
| 60 | +returnmaxProfit; |
| 61 | + } |
| 62 | +} |