123:Best Time to Buy and Sell Stock III【数组】【DP】

浏览数：28 / 时间：2015年06月08日

题目链接：click~

/*题意：一个数组，第i元素表示第i天股票的价格，允许最多买卖两次，求最大利润 */

/**
 *思路：用currProfit数组记录截止当日的最大利润，从头到尾扫描一遍数组即可获得
 *      currProfit = max(currPorfit[i], prices[i]-low)
 *
 *      用futureProfit数组记录当日以后的最大利润，从尾到头扫描可得
 *      futureProfit = max(futureProfit[i], high-prices[i])
 *
 *      计算总利润：anx = max(ans, currProfit[i]+futureProfit[i])
 */

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int len = prices.size();
        if(len <= 1) return 0;
        int *currProfit = new int[len];
        int *futureProfit = new int[len];
        currProfit[0] = futureProfit[len-1] = 0;

        //记录截止当日的最大利润
        int low = prices[0];
        for(int i = 1; i < len; i ++) {
            low = min(low, prices[i]);
            currProfit[i] = max(currProfit[i-1], prices[i]-low);
        }

        //计算该日以后的最大利润
        int high = prices[len-1];
        for(int i = len-2; i >= 0; i --) {
            high = max(high, prices[i]);
            futureProfit[i] = max(futureProfit[i+1], high-prices[i]);
        }

        //合计
        int ans = 0;
        for(int i = 0; i < len; i ++)
            ans = max(ans, currProfit[i] + futureProfit[i]);
        return ans;
    }
};

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。