Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III

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).

------------------------------------------------thinking-------------------------------------------
the first loop is from left to right, using an array to record the cur maximum result we can get, then the second loop is from right to left, based on the sum of maximum array and current max, we can get the final result we need.

Additional question: How to do the calculation if the them is three?

------------------------------------------------ reading codes -----------------------------------------
https://oj.leetcode.com/discuss/18330/is-it-best-solution-with-o-n-o-1
This method is quite like the question of finding singleton in duplications
http://yingshuntingjournal.blogspot.com/2015/02/single-number-ii.html

public class Solution { public int maxProfit(int[] prices) { int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE; int release1 = 0, release2 = 0; for(int i:prices){ // Assume we only have 0 money at first release2 = Math.max(release2, hold2+i); // The maximum if we've just sold 2nd stock so far. hold2 = Math.max(hold2, release1-i); // The maximum if we've just buy 2nd stock so far. release1 = Math.max(release1, hold1+i); // The maximum if we've just sold 1nd stock so far. hold1 = Math.max(hold1, -i); // The maximum if we've just buy 1st stock so far. } return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1. } }
------------------------------------------------ codes ----------------------------------------------------
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.size() == 0) {
            return 0;
        }
        vector<int> max;
        int cur_min = prices[0];
        max.push_back(0);
        for(int i = 1; i < prices.size(); i++) {
            if (prices[i] < cur_min) {
                cur_min = prices[i];
            }
            if (prices[i] - cur_min > max[i-1]) {
                max.push_back(prices[i] - cur_min);
            } else {
                max.push_back(max[i-1]);
            }
        }
        int cur_max = prices[prices.size() - 1];
        int result = max[prices.size() - 1];
        for (int i = prices.size() - 2; i >= 0; i--) {
            if (prices[i] > cur_max) {
                cur_max = prices[i];
            }
            if (cur_max - prices[i] + max[i] > result) {
                result = cur_max - prices[i] + max[i];
            }
        }
        return result;
    }
};