[LeetCode] Best Time to Buy and Sell Stock III

Say you have an array for which the .

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******************************************************************/;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;}

，一错再错，把握正确的方向，