Best Time to Buy and Sell Stock III

Description

Example

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    int maxProfit(vector<int> &prices) {
        // write your code here
        if (prices.size() < 2) {
            return 0;
        }
        int len = prices.size();
        vector<int> forward(len, 0);
        vector<int> backward(len, 0);
        // forward buy
        // use current price minus min val, then record the sell time
        forward[0] = 0;
        int minval = prices[0];
        for (int i = 1; i< len; ++i) {
            // int diff = prices[i] - prices[i-1];
            minval = min(minval, prices[i]);
            forward[i] = max(forward[i-1], prices[i] - minval);
        }
        // backward buy
        // use max price minus current val, then reocrd the buy time
        backward[len-1] = 0;
        int maxval = prices[len-1];
        for (int i = len - 2; i >= 0; --i) {
            // int diff = prices[i+1] - prices[i];
            maxval = max(maxval, prices[i]);
            backward[i] = max(backward[i+1], maxval - prices[i]);
        }
        int maxprofit = 0;
        for (int i = 0; i < len; ++i) {
            maxprofit = max(maxprofit, forward[i] + backward[i]);
        }
        return maxprofit;
    }
};

Similar problems

x

Tags

x