# 121. Best Time to Buy and Sell Stock

[leetcode網址](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/)

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

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](https://neetcode.io/courses/advanced-algorithms/0)，就可以只用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;
}