@requires_authorization

@author johnsondu

@create_time 2015.7.22 19:04

@url [Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/)

/************************

 * @description: dynamic programming.

 *    从前后分别求出当前所能够得到的最大值，最后相加而得

 *    详细操作是，设置一个最小值，然后不断更新最小值。然后不断更新最大值。

前后反向累加求得最大值

 * @time_complexity:  O(n)

 * @space_complexity: O(n)

 ************************/

 class Solution {

public:

    int maxProfit(vector<int>& prices) {

        const int len = prices.size();

        if(len < 2) return 0;

        int maxFromHead[len];

        maxFromHead[0] = 0;

        int minprice = prices[0], maxprofit = 0;

        for(int i = 1; i < len; i ++) {

            minprice = min(prices[i-1], minprice);

            if(maxprofit < prices[i] - minprice)

                maxprofit = prices[i] - minprice;

            maxFromHead[i] = maxprofit;

        }

        int maxprice = prices[len-1];

        int res = maxFromHead[len-1];

        maxprofit = 0;

        for(int i = len-2; i >= 0; i --) {

            maxprice = max(maxprice, prices[i+1]);

            if(maxprofit < maxprice - prices[i])

                maxprofit = maxprice - prices[i];

            if(res < maxFromHead[i] + maxprofit)

                res = maxFromHead[i] + maxprofit;

        }

        return res;

    }

};

@requires_authorization

@author johnsondu

@create_time 2015.7.22 19:04

@url [Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/)

/************************

 * @description: dynamic programming.

 *    超时做法：从1開始。分成前后两段，最后求得前后两段的最大值

 * @time_complexity:  O(n^2)

 * @space_complexity: O(n)

 ************************/

class Solution {

public:

    int maxProfit(vector<int>& prices) {

        int p_size = prices.size();

        if(p_size < 2) return 0;

        if(p_size < 3) {

            return prices[1] - prices[0] > 0 ?

prices[1] - prices[0]: 0;

        }

        int ans = 0;

        for(int i = 1; i < p_size; i ++) {

            vector<int> dp1, dp2;

            for(int j = 1; j <= i; j ++) {

                dp1.push_back(prices[i] - prices[i-1]);

            }

            for(int j = i + 1; j < p_size; j ++) {

                dp2.push_back(prices[j] - prices[j-1]);

            }

            int dp1_size = dp1.size();

            int ans1 = 0;

            int cur = 0;

            for(int j = 0; j < dp1_size; j ++) {

                cur = cur + dp1[j];

                if(cur < 0) {

                    cur = 0;

                    continue;

                }

                if(cur > ans1) ans1 = cur;

            }

            int dp2_size = dp2.size();

            int ans2 = 0;

            cur = 0;

            for(int j = 0; j < dp2_size; j ++) {

                cur = cur + dp2[j];

                if(cur < 0) {

                    cur = 0;

                    continue;

                }

                if(cur > ans2) ans2 = cur;

            }

            ans = max(ans, ans1 + ans2);

        }

        return ans;

    }

};