题解 | #牛群买卖计划#

题目考察的知识点：动态规划

题目解答方法的文字分析：f数组表示买入状态时的最大利润，g数组表示卖出状态时的最大利润，可以交易3次，所以可能有0/1/2/3共四种交易次数，所以创建一个4乘n的数组；f，g为dp表，然后初始化dp表；填表，返回四种交易次数中利润最大的。

本题解析所用的编程语言：c++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    const int INF = 0x3f3f3f3f;
    int maxProfit(vector<int>& prices) {
        // write code here
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(4, -INF)), g(n, vector<int>(4, -INF));
        f[0][0] = -prices[0], g[0][0] = 0;
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < 4; ++j)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                if (j >= 1)
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
                else 
                    g[i][j] = g[i - 1][j];
            }
        }
        int ret = 0;
        for (int j = 0; j < 4; ++j)
            ret = max(ret, g[n - 1][j]);
        return ret;
    }
};