# [LeetCode] 123. Best Time to Buy and Sell Stock III 买卖股票的最佳时间 III

2021年09月15日 阅读数：3

Say you have an array for which the ith element is the price of a given stock on day i.html

Design an algorithm to find the maximum profit. You may complete at most two transactions.java

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).python

Example 1:数组

```Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.```

Example 2:app

```Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
```

Example 3:ide

```Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.```

prices[0:n-1] => prices[0:i] + prices[i:n-1]，对于这个分割来讲，最大收益为两段的最大收益之和。每一段的最大收益用I的解法来作。最大收益是对全部0<=i<=n-1的分割的最大收益取一个最大值。url

1. 计算A[0:i]的收益最大值：用minPrice记录i左边的最低价格，用maxLeftProfit记录左侧最大收益
2. 计算A[i:n-1]的收益最大值：用maxPrices记录i右边的最高价格，用maxRightProfit记录右侧最大收益。
3. 最后这两个收益之和即是以i为分割的最大收益。将序列从左向右扫一遍能够获取dp1，从右向左扫一遍能够获取dp2。相加后取最大值即为答案。htm

Java：Divide and conquer

```public class Solution {
public int maxProfit(int[] prices) {
// find maxProfit for {0, j}, find maxProfit for {j + 1, n - 1}
// find max for {max{0, j}, max{j + 1, n - 1}}

if (prices == null || prices.length == 0) {
return 0;
}

int maximumProfit = 0;
int n = prices.length;

ArrayList<Profit> preMaxProfit = new ArrayList<Profit>(n);
ArrayList<Profit> postMaxProfit = new ArrayList<Profit>(n);
for (int i = 0; i < n; i++) {
postMaxProfit.add(maxProfitHelper(prices, i + 1, n - 1));
}
for (int i = 0; i < n; i++) {
int profit = preMaxProfit.get(i).maxProfit + postMaxProfit.get(i).maxProfit;
maximumProfit = Math.max(profit, maximumProfit);
}
return maximumProfit;
}

private Profit maxProfitHelper(int[] prices, int startIndex, int endIndex) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int i = startIndex; i <= endIndex; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
}
if (prices[i] - minPrice > maxProfit) {
maxProfit = prices[i] - minPrice;
}
}
return new Profit(maxProfit, minPrice);
}

public static void main(String[] args) {
int[] prices = new int[]{4,4,6,1,1,4,2,5};
Solution s = new Solution();
System.out.println(s.maxProfit(prices));
}
};

class Profit {
int maxProfit, minPrice;
Profit(int maxProfit, int minPrice) {
this.maxProfit = maxProfit;
this.minPrice = minPrice;
}
}
```

Java：DP

```public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}

int[] left = new int[prices.length];
int[] right = new int[prices.length];

// DP from left to right;
left[0] = 0;
int min = prices[0];
for (int i = 1; i < prices.length; i++) {
min = Math.min(prices[i], min);
left[i] = Math.max(left[i - 1], prices[i] - min);
}

//DP from right to left;
right[prices.length - 1] = 0;
int max = prices[prices.length - 1];
for (int i = prices.length - 2; i >= 0; i--) {
max = Math.max(prices[i], max);
right[i] = Math.max(right[i + 1], max - prices[i]);
}

int profit = 0;
for (int i = 0; i < prices.length; i++){
profit = Math.max(left[i] + right[i], profit);
}

return profit;
}
}
```

Python：T：O(n), S: O(n)

```class Solution3:
def maxProfit(self, prices):
min_price, max_profit_from_left, max_profits_from_left = float("inf"), 0, []
for price in prices:
min_price = min(min_price, price)
max_profit_from_left = max(max_profit_from_left, price - min_price)
max_profits_from_left.append(max_profit_from_left)

max_price, max_profit_from_right, max_profits_from_right = 0, 0, []
for i in reversed(range(len(prices))):
max_price = max(max_price, prices[i])
max_profit_from_right = max(max_profit_from_right, max_price - prices[i])
max_profits_from_right.insert(0, max_profit_from_right)

max_profit = 0
for i in range(len(prices)):
max_profit = max(max_profit, max_profits_from_left[i] + max_profits_from_right[i])

return max_profit
```

Python:

```class Solution:
def maxProfit(self, prices):
hold1, hold2 = float("-inf"), float("-inf")
release1, release2 = 0, 0
for i in prices:
release2 = max(release2, hold2 + i)
hold2    = max(hold2,    release1 - i)
release1 = max(release1, hold1 + i)
hold1    = max(hold1,    -i);
return release2　　```

C++：DP

```class Solution {
public:
int maxProfit(vector<int> &prices) {
if(prices.empty()) return 0;
int n = prices.size();
vector<int> leftProfit(n,0);

int maxLeftProfit = 0, minPrice = prices[0];
for(int i=1; i<n; i++) {
if(prices[i]<minPrice)
minPrice = prices[i];
else
maxLeftProfit = max(maxLeftProfit, prices[i]-minPrice);
leftProfit[i] = maxLeftProfit;
}

int ret = leftProfit[n-1];
int maxRightProfit = 0, maxPrice = prices[n-1];
for(int i=n-2; i>=0; i--) {
if(prices[i]>maxPrice)
maxPrice = prices[i];
else
maxRightProfit = max(maxRightProfit, maxPrice-prices[i]);
ret = max(ret, maxRightProfit + leftProfit[i]);
}

return ret;
}
};
```

[LeetCode] 121. Best Time to Buy and Sell Stock 买卖股票的最佳时间

[LeetCode] 122. Best Time to Buy and Sell Stock II 买卖股票的最佳时间 II

[LeetCode] 188. Best Time to Buy and Sell Stock IV 买卖股票的最佳时间 IV

[LeetCode] 309. Best Time to Buy and Sell Stock with Cooldown 买卖股票的最佳时间有冷却期