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.

http://www.lintcode.com/en/problem/best-time-to-buy-and-sell-stock-iii/

Discussion

设状态f(i)，表示区间[0, i]的最大利润，状态g(i)，表示区间[i, n-1] 的最大利润，则最终答案为max {f(i) + g(i)}。 允许在一天内买进又卖出，相当于不交易，因为题目的规定是最多两次，而不是一定要两次。

Solution

class Solution {
public:
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    int maxProfit(vector<int> &prices) {
        // write your code here
        int n = prices.size();
        if(n==0) return 0;
        vector<int> profitForward(n, 0);
        vector<int> profitBackward(n, 0);
        int localmin = prices[0];
        for(int i=1; i<n; i++) {
            localmin = min(prices[i], localmin);
            profitForward[i] = max(profitForward[i-1], prices[i]-localmin);
        }
        int localmax = prices[n-1];
        for(int i=n-2; i>=0; i--) {
            localmax = max(localmax, prices[i]);
            profitBackward[i] = max(profitBackward[i+1], localmax-prices[i]);
        }
        int result = 0;
        for(int i=0; i<n; i++) {
            result = max(result, profitForward[i]+profitBackward[i]);
        }
        return result;
    }
};

kamyu104的解法：

// Time:  O(n)
// Space: O(1)

// DP Solution
class Solution {
public:
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    int maxProfit(vector<int> &prices) {
        if (prices.empty()) {
            return 0;
        }

        int hold1 = INT_MIN, hold2 = INT_MIN;
        int release1 = INT_MIN, release2 = INT_MIN;

        for (const auto& p : prices) {
            hold1 = max(hold1, -p);
            release1 = max(release1, hold1 + p);
            hold2 = max(hold2, release1 - p);
            release2 = max(release2, hold2 + p);
        }

        return release2;
    }
};

// Generic Solution
class Solution2 {
public:
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    int maxProfit(vector<int> &prices) {
        if (prices.empty()) {
            return 0;
        }

        const int k = 2;

        // Optimized solution for unlimited transactions.
        if (k >= prices.size() / 2) {
            return maxUnlimitedTransactionsProfit(prices);
        }

        // Get max profit at most k transactions.
        return maxAtMostKTransactionsProfit(prices, k);
    }

    int maxUnlimitedTransactionsProfit(vector<int> &prices) {
        int profit = 0;
        for (int i = 0; i < prices.size() - 1; ++i) {
            profit += max(0, prices[i + 1] - prices[i]);
        }
        return profit;
    }

    int maxAtMostKTransactionsProfit(vector<int> &prices, int k) {
        // max_sell[j] short for max_sell[i][j]
        // denotes as max profit at most j - 1 buy and sell transactions
        // and buy the ith prices in the first i prices.
        vector<int> max_sell(k + 1, INT_MIN);

        // max_buy[j] short for max_buy[i][j]
        // denotes as max profit at most j buy and sell transactions
        // and sell the ith prices in the first i prices.
        vector<int> max_buy(k + 1, INT_MIN);

        max_sell[0] = max_buy[0] = 0;

        for (int i = 0; i < prices.size(); ++i) {
            // Update max profix in [i / 2]  + 1 transactions.
            for (int j = 1; j <= min(k, i / 2 + 1); ++j) {
                // Update max profit of j-th buy
                // by (j-1)-th sell - prices[i].
                max_buy[j] = max(max_buy[j], max_sell[j - 1] - prices[i]);

                // Update max profit of jth sell
                // by max(j-th buy + prices[i], (j-1)-th sell]).
                max_sell[j] = max(max_sell[j], max_buy[j] + prices[i]);
            }
        }

        return max_sell[k];
    }
};