题解 | #牛群买卖计划III# 贪心

知识点

贪心

思路

由于可以在某一天卖出之前的所有牛，为了利益最大化，我们需要在价格最高的那天卖出之前的购入的所有牛，在价格次之的一天卖出之前的所有牛（排除之前已经卖出的）……

因此我们可以对价格从高到低排序，每次从卖出日向前枚举找到没有卖出的一段卖出，累计答案。

时间复杂度

AC Code (C++)

#include <numeric>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfitIII(vector<int>& prices) {
        int n = prices.size();
        vector<int> q(n);
        iota(q.begin(), q.end(), 0);
        sort(q.begin(), q.end(), [&](int x, int y) {
            return prices[x] > prices[y];
        });
        int res = 0;
        vector<bool> st(n, false);
        for (int i = 0; i < n; i ++) {
            int id = q[i];
            st[id] = true;
            for (int j = id - 1; j >= 0 and !st[j]; j --) {
                res += prices[id] - prices[j];
                st[j] = true;
            }
        }
        return res;
    }
};