# Best Time to Buy and Sell Stock III

## Question

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

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

Example
Given an example [4,4,6,1,1,4,2,5], return 6.

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


## 题解

### Python

class Solution:
"""
@param prices: Given an integer array
@return: Maximum profit
"""
def maxProfit(self, prices):
if prices is None or len(prices) <= 1:
return 0

n = len(prices)
# get profit in the front of prices
profit_front = [0] * n
valley = prices[0]
for i in xrange(1, n):
profit_front[i] = max(profit_front[i - 1], prices[i] - valley)
valley = min(valley, prices[i])
# get profit in the back of prices, (i, n)
profit_back = [0] * n
peak = prices[-1]
for i in xrange(n - 2, -1, -1):
profit_back[i] = max(profit_back[i + 1], peak - prices[i])
peak = max(peak, prices[i])
# add the profit front and back
profit = 0
for i in xrange(n):
profit = max(profit, profit_front[i] + profit_back[i])

return profit


### C++

class Solution {
public:
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
int maxProfit(vector<int> &prices) {
if (prices.size() <= 1) return 0;

int n = prices.size();
// get profit in the front of prices
vector<int> profit_front = vector<int>(n, 0);
for (int i = 1, valley = prices[0]; i < n; ++i) {
profit_front[i] = max(profit_front[i - 1], prices[i] - valley);
valley = min(valley, prices[i]);
}
// get profit in the back of prices, (i, n)
vector<int> profit_back = vector<int>(n, 0);
for (int i = n - 2, peak = prices[n - 1]; i >= 0; --i) {
profit_back[i] = max(profit_back[i + 1], peak - prices[i]);
peak = max(peak, prices[i]);
}
// add the profit front and back
int profit = 0;
for (int i = 0; i < n; ++i) {
profit = max(profit, profit_front[i] + profit_back[i]);
}

return profit;
}
};


### Java

class Solution {
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) return 0;

// get profit in the front of prices
int[] profitFront = new int[prices.length];
profitFront[0] = 0;
for (int i = 1, valley = prices[0]; i < prices.length; i++) {
profitFront[i] = Math.max(profitFront[i - 1], prices[i] - valley);
valley = Math.min(valley, prices[i]);
}
// get profit in the back of prices, (i, n)
int[] profitBack = new int[prices.length];
profitBack[prices.length - 1] = 0;
for (int i = prices.length - 2, peak = prices[prices.length - 1]; i >= 0; i--) {
profitBack[i] = Math.max(profitBack[i + 1], peak - prices[i]);
peak = Math.max(peak, prices[i]);
}
// add the profit front and back
int profit = 0;
for (int i = 0; i < prices.length; i++) {
profit = Math.max(profit, profitFront[i] + profitBack[i]);
}

return profit;
}
};


## Reference

• soulmachine 的卖股票系列