暴力超时版本

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         if(prices.size() <=0){
  5.             return 0;
  6.         }
  8.         int n = prices.size();
  9.         int dp1 = 0;
  10.         for (int i = 0; i < n; i++)
  11.         {
  12.             dp1 = max(dp1, 
  13.             maxRange(prices, 0, i) + maxRange(prices, i, n));
  14.         }
  16.         return dp1;
  17.     }
  20.     int maxRange(vector<int>& prices, int start, int end){
  22.         int dp = 0;
  23.         int minP = 0;
  24.         minP = prices[start];
  25.         for (int i = start; i < end; i++)
  26.         {
  27.             dp = max(dp , prices[i] - minP);
  28.             if(prices[i] < minP){
  29.                 minP = prices[i];
  30.             }
  32.         }
  33.         return dp;
  34.     }
  35. };

优化版本

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() <=0){
            return 0;
        }
        int n = prices.size();
        vector<int> min_f(n+1, 0);
        vector<int> max_p(n+1, 0);
        vector<int> max_b(n+1, 0);
        min_f[0] = prices[0];
        for(int i = 1; i<prices.size(); i++){
            min_f[i] = min(prices[i], min_f[i - 1]);
        }
        max_b[prices.size() - 1] = prices[prices.size() - 1];
        max_p[n-1] = 0;
        for(int i = prices.size() - 2; i>=0; i--){
            max_b[i] = max(prices[i], max_b[i + 1]);
            max_p[i] = max(max_b[i] - prices[i],  max_p[i+1]);
        }
        int dp1 = 0;
        for (int i = 0; i < n -1; i++)
        {
            dp1 = max(dp1, prices[i] - min_f[i] +  max_p[i]);
        }
        dp1 = max(dp1, prices[n-1]- min_f[n-1] + max_p[n-1]);
        return dp1;
    }

};