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

class Solution {
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    /*动态规划
    int maxProfit(vector<int>& prices) {
        // write code here
        int n = prices.size();
        vector<int> dp(n);
        dp[0] = 0;
        int maxv = dp[0];
        for (int i = 1; i < n; i ++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + (prices[i] - prices[i - 1]);
            }
            else {
                dp[i] = prices[i] - prices[i - 1];
            }
            maxv = max(maxv, dp[i]);
        }
        return maxv;
    }
    */
    
    //贪心算法
    int maxProfit(vector<int>& prices) {
        int minv = prices[0];
        int profit = 0;
        for (int i = 0; i < prices.size(); i ++) {
            minv = min(minv, prices[i]);
            profit = max(profit, prices[i] - minv);
        }
        return profit;
    }
};