题解 | #牛群买卖策略优化#

知识点

贪心，模拟

思路

首先，我们知道牛在同一天买卖是没有意义的（因为利润为0）。所以我们只需要考虑隔天买卖的情况。

假设price数组的长度为n。假设对于i，有price[i~j]都为递增，那么只需要你在第i天买，第j天卖，即可获得最大利润（在中间买卖也没有意义，因为无利润）

所以我们只需要遍历price，对每一个i，寻找右侧最大的递增末位，不断更新ans即可，ans+=price[j]-price[i]，然后把i赋值为j，因为这段区间[i~j]已经不需要再进行交易了，利润已经被榨干了。

代码c++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int max_profitv2(vector<int>& prices) {
        // write code here
        int ans=0;
        int n=prices.size();
        for(int i=0;i<prices.size();i++)
        {
            
                int j=i;
                while(j+1<n&&prices[j]<prices[j+1])j++;//j+1的上界不能超过n

                ans+=(prices[j]-prices[i]);//更新利润
                i=j;//更新下一个区间的起点
            

        }
        return ans;
    }
};