121.best-time-to-buy-and-sell-stock 买卖股票的最佳时机

问题描述

121.买卖股票的最佳时机

解题思路

动态规划

dp[i]表示前i天的最大收益，那么dp[i]的递推公式为:dp[i] = min(dp[i - 1], a[i - 1] - min(price[0, i - 1)), 0)。

贪心算法

利用cur记录最小元素，碰到更小的就替换cur的值，遇到比它大的就进行一次利润计算，保存最大的利润。

代码

class Solution {
  private:
    int min(int a, int b) {
        return a < b ? a : b;
    }
    int max(int a, int b, int c) {
        if (a > b)
            return a > c ? a : c;
        else
            return b > c ? b : c;
    }

  public:
    int maxProfit(vector<int> &prices) {
        if (prices.size() == 1)
            return 0;
        vector<int> min_arr(prices.size() + 1, prices[0]);
        min_arr[0] = prices[0];
        for (int i = 1; i <= prices.size(); i++) {
            min_arr[i] = min(min_arr[i - 1], prices[i - 1]);
        }
        vector<int> dp(prices.size() + 1, 0);
        for (int i = 1; i <= prices.size(); i++) {
            dp[i] = max(dp[i - 1], prices[i - 1] - min_arr[i - 1], 0);
        }
        return dp[prices.size()];
    }
};