Commit 582bc27
authored
Create leetcode_123_118.java
1 parent 4a5f123 commit 582bc27
1 file changed
Lines changed: 57 additions & 0 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,57 @@ | |||
| 1 | + // https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/ | ||
| 2 | + // 123.买卖股票的最佳时机3 | ||
| 3 | + // 是在 122 的基础上，加了限制条件，不能对所有值做累加，只能取最大的两个求和 | ||
| 4 | + class Solution { | ||
| 5 | + public int maxProfit(int[] prices) { | ||
| 6 | + | ||
| 7 | + ArrayList<Integer> profit = new ArrayList(); | ||
| 8 | + | ||
| 9 | + // 1. 数组为空，或只有一个元素，则最大利润为0 | ||
| 10 | + if(prices.length<=1){ | ||
| 11 | + return 0; | ||
| 12 | + } | ||
| 13 | + | ||
| 14 | + int totalMaxProfit = 0; | ||
| 15 | + | ||
| 16 | + // | ||
| 17 | + for(int i=1;i<prices.length;i++){ | ||
| 18 | + // 左侧闭区间：[0,i] | ||
| 19 | + // 右侧闭区间：[i+1,length-1] | ||
| 20 | + int leftMaxProfit = maxProfit(prices,0,i); | ||
| 21 | + int rightMaxProfit = maxProfit(prices,i+1,prices.length-1); | ||
| 22 | + if(leftMaxProfit+rightMaxProfit >totalProfit){ | ||
| 23 | + totalProfit = leftMaxProfit+rightMaxProfit; | ||
| 24 | + } | ||
| 25 | + } | ||
| 26 | + | ||
| 27 | + return totalProfit; | ||
| 28 | + } | ||
| 29 | + | ||
| 30 | + | ||
| 31 | + // 求闭区间 [from,to] 做一笔交易的最大值。 | ||
| 32 | + int maxProfit(int[] prices,int from,int to){ | ||
| 33 | + if(from>=to){ | ||
| 34 | + return 0; | ||
| 35 | + } | ||
| 36 | + if(from+1==to){ | ||
| 37 | + return prices[to]-prices[from]>0?prices[to]-prices[from]:0; | ||
| 38 | + } | ||
| 39 | + | ||
| 40 | + int minPrice = prices[from]; | ||
| 41 | + int maxProfit = 0; | ||
| 42 | + for(int i=from+1;i<prices.length && i<=to;i++){ | ||
| 43 | + // 若今天价格高于前面几天的最低价格，则可以卖出。 | ||
| 44 | + // 此时，计算今天卖出利润多少，是否比已计算的利润更高 | ||
| 45 | + if(prices[i]>minPrice && maxProfit<(prices[i]-minPrice)){ | ||
| 46 | + maxProfit = prices[i]-minPrice; | ||
| 47 | + } | ||
| 48 | + | ||
| 49 | + // 若今天价格低于前几天的最低价格，则更新最低价格 | ||
| 50 | + if(prices[i]<minPrice){ | ||
| 51 | + minPrice = prices[i]; | ||
| 52 | + } | ||
| 53 | + } | ||
| 54 | + | ||
| 55 | + return maxProfit; | ||
| 56 | + } | ||
| 57 | + } | ||
0 commit comments