[LeetCode] Best Time to Buy and Sell Stock III

Say you have an array for which the ithi^{th} element is the price of a given stock on day ii. Design an algorithm to find the maximum profit. You may complete at most two transactions.

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.

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

建立两个数组left和right，分别存储某个元素左边和右边所能获得的最大收益。即left[i]存储从[0, i]范围的最大收益；right[i]存储从[i, len - 1]范围的最大收益。

/*****************************************************************

 * @Author : 楚兴

 * @Date : 2015/2/22 18:08

 * @Status : Accepted

 * @Runtime : 16 ms

******************************************************************/

#include iostream 

#include vector 

#include algorithm 

using namespace std;

class Solution {

public:

 int maxProfit(vector int prices) {

 int len = prices.size();

 if (len == 0)

 return 0;

 vector int left(len, 0);

 vector int right(len, 0);

 int i = 0;

 int low = prices[0];

 int profit = 0;

 while (i len - 1)

 if (prices[i] low)

 low = prices[i];

 else if (prices[i] = prices[i + 1])

 profit = max(profit, prices[i] - low);

 left[i] = profit;

 i++;

 profit = max(profit, prices[i] - low);

 left[i] = profit;

 int high = prices[i];

 profit = 0;

 while(i 0)

 if (prices[i] high)

 high = prices[i];

 else if (prices[i] = prices[i - 1])

 profit = max(profit, high - prices[i]);

 right[i] = profit;

 i--;

 profit = max(profit, high - prices[i]);

 right[i] = profit;

 i = 0;

 int max_profit = 0;

 while (i len)

 max_profit = max(max_profit, left[i] + right[i]);

 i++;

 return max_profit;

int main()

 int num[] = {1,2,3,4,5,6};

 vector int n(num, num + sizeof(num)/sizeof(int));

 Solution s;

 int profit = s.maxProfit(n);

 cout profit endl;

}

另一种解题思路可参考Best Time to Buy and Sell Stock IV。

LeetCode 121. Best Time to Buy and Sell Stock 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果您最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
LeetCode 123. Best Time to Buy and Sell Stock III 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
LeetCode 188. Best Time to Buy and Sell Stock IV 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。