题解 | #买卖股票的最好时机(三)#

买卖股票的最好时机(三)

http://www.nowcoder.com/practice/4892d3ff304a4880b7a89ba01f48daf9

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        if (prices.size() == 0) return 0;
        /*
        5个状态:1)不操作2)第一次购买3)第一次卖出4)第二次购买5)第二次卖出
        dp[i][j]代表第i天状态为j时产生的最大收益
        */
        int dp[200005][5]={0};
        //初始化
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = dp[i - 1][0];
            //其中dp[i][1]有两个操作1)第i天没有操作2)第i天买入股票,所以此时最大收益,应该为这两个操作比大小
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            //其中dp[i][2]有两个操作1)第i天没有操作2)第i天卖出股票,所以此时最大收益,应该为这两个操作比大小
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            //其中dp[i][3]有两个操作1)第i天没有操作2)第i天买入股票,所以此时最大收益,应该为这两个操作比大小
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            //其中dp[i][4]有两个操作1)第i天没有操作2)第i天卖出股票,所以此时最大收益,应该为这两个操作比大小
            dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        return dp[prices.size() - 1][4];
    }
};
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务