Leetcode 详解（股票交易日）（动态规划DP）

问题描述：

在股市的交易日中，假设最多可进行两次买卖(即买和卖的次数均小于等于2)，规则是必须一笔成交后进行另一笔(即买-卖-买-卖的顺序进行)。给出一天中的股票变化序列，请写一个程序计算一天可以获得的最大收益。请采用实践复杂度低的方法实现。

给定价格序列prices及它的长度n，请返回最大收益。保证长度小于等于500。

class Solution {

    public:

    int maxProfit(vector<int>& prices) {

    //It's wrong if you choose the minimum price for buy2 , but you can maximize the left money.

    //

    int buy1 = INT_MIN, sale1 = 0, buy2 = INT_MIN, sale2 = 0;

    for(int i=0; i<prices.size(); i++){                      //the more money left, the happier you will be

        buy1 = max(buy1, -prices[i]);                        //left money after buy1

        sale1 = max(sale1, prices[i] + buy1);                //left money after sale1

        buy2 = max(buy2, sale1 - prices[i]);                 //left money after buy2

        sale2 = max(sale2, prices[i] + buy2);                //left money after sale2

    }

    return sale2;

    }

};

此方法的核心是对于每个数据，我都以相同的处理方法（动态规划），在此，把问题解决转化为手头的剩余的钱的变化， 每一步的处理都是为了手上留下的钱更多。