原題
LintCode 151. Best Time to Buy and Sell Stock III
Description
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.
Notice
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Example
Given an example [4,4,6,1,1,4,2,5], return 6.
解題
給出股票價格的變化，只能每天只能買入或賣出一次凿滤，求利潤最大值您没。
要求總交易次數(shù)不超過兩次芽死，且必須處理完一次交易后（買入并賣出后）才能繼續(xù)下一次交易。
要求兩次交易之間沒有重合劲绪，那么可以采用分治的方法绢陌。將數(shù)組以i為借分為兩個部分求出這兩個部分的最大利潤，再相加侠仇。
定義front[i]表示0 到 i的最大利潤，back[i]表示i 到 n - 1的最大利潤犁珠，然后再對所有i進(jìn)行一次遍歷逻炊，取front[i] + back[i]的最大值即可互亮。
front[i]和back[i]可以用動態(tài)規(guī)劃的思想計算。
代碼
class Solution {
public:
/*
* @param prices: Given an integer array
* @return: Maximum profit
*/
int maxProfit(vector<int> &prices) {
// write your code here
if (prices.size() < 2) return 0;
vector<int> front(prices.size()), back(prices.size());
for (int i = 1, minPrice = prices.front(); i < prices.size(); i++) {
minPrice = min(minPrice, prices[i]);
front[i] = max(front[i - 1], prices[i] - minPrice);
}
for (int i = prices.size() - 2, maxPrice = prices.back(); i >= 0; i--) {
maxPrice = max(maxPrice, prices[i]);
back[i] = max(back[i + 1], maxPrice - prices[i]);
}
int res = 0;
for (int i = 0; i < prices.size(); i++) {
res = max(res, front[i] + back[i]);
}
return res;
}
};
