WEI-CHENG CHEN

說明

你只能買入一次並賣出一次，求最大的利潤是多少

解法 01：暴力解

定一個點(for loop)，然後另一個 for 去跑後面的，不斷紀錄最小值。

解法 02：DP

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int maxprofit = 0; // 最大獲利
        int minprice = INT_MAX; // 過去紀錄的最低價格
        for(int i=0;i<n;i++){
            maxprofit = max(maxprofit, (prices[i]-minprice)); // 更新最大差距
            minprice = min(minprice, prices[i]); // 更新最低點
        }
        return maxprofit;
    }
};