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

#include <algorithm>
#include <vector>
class Solution {
public:

    int maxProfit(vector<int>& prices) 
    {
       //连续子数组的最大和 问题变种
       //每天和前一天的差价就是当天的利润，买入那天就是连续子数组的开头，卖掉那天就是连续子数组的结尾


       int n = prices.size();

       if (n < 2) 
       {
            return 0;
       }

       vector<int> pf(n,0);     //利润
       
       pf[0] = -prices[0];
       for(int i = 1; i < n; i++)
       {
            pf[i] = prices[i] - prices[i-1];
       }

        vector<int> dp(n,0);
        dp[0] = pf[0];
        for(int i = 1; i < n; i++)
       {
            dp[i] = max(pf[i],dp[i-1] + pf[i]);
       }

       auto it = max_element(dp.begin(), dp.end());
       if (*it < 0) 
       {
            return 0;
       }
       
       return *it;
    }
};