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). http://www.leetcode.com/onlinejudge

leetcode_best_time_to_buy_and_sell_stock3.cpp

#include <algorithm>
using namespace std;

class Solution {
public:
    int maxProfit_one(vector<int>::iterator left, vector<int>::iterator right) {
        int ret = 0;
        int mini = 0x7fffffff;
        vector<int>::iterator it;
        for (it = left; it != right; ++it) {
            ret = max(ret, *it - mini);
            mini = min(mini, *it);
        }
        return ret;
    }

    int maxProfit(vector<int> &prices) {
        int ret = maxProfit_one(prices.begin(), prices.end());
        vector<int>::iterator it;
        for (it = prices.begin(); it != prices.end(); ++it) {
            if (it != prices.begin() && it + 1 != prices.end() && (*it > *(it - 1) && *it >= *(it + 1))) {
                ret = max(ret, maxProfit_one(prices.begin(), it + 1) + maxProfit_one(it + 1, prices.end()));
            }
        }
        return ret;
    }
};