121. Best Time to Buy and Sell Stock

leetcode網址

問題

找到最低價購入，並在最高價時售出，購入時間必須在售出前，最後回傳利潤是多少

Input: prices = [7,1,5,3,6,4]
Output: 5
        Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
        Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Idea

用Kadane's algorithm，就可以只用O(N)的時間複雜度

1. 用一個變數來keep最低價 mini
2. 每次只要price-mini有比 profit 大就更新profit，

走完整個序列，在過程中keep一個值來找出最大差的方式就是Kadane's Algorithm，算是一種DP的方法，可以將

$O(N^2)$的問題降低成

$O(N)$

Solution

int maxProfit(vector<int>&prices){
    int mini=INT_MAX, profit=0;
    
    for(auto&price: prices){
        mini = min(price, mini);
        profit = max(price-mini, profit);
    }
    return profit;
}