# Leetcode [No.121] Best Time to Buy and Sell Stock (EASY)

## 題目

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

## 思路
+ 這個題目就是典型使用dp的題目，我利用dp table來記錄現在最便宜的買點。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<int> dp(prices.size());
        dp[0] = prices[0]; // dp vector is used to save min prices
        int maxProfit = 0;
        for (int i = 1 ; i < prices.size(); i++)
        {
            dp[i] = (min(dp[i-1], prices[i]));
            maxProfit = max(maxProfit, prices[i] - dp[i]);
        }
        return maxProfit;
    }
};

### 解法分析
+ time complexity: O(n)

### 執行結果

---

## 改良

+ 突然想到用一個table來記錄最低買點好像有點雞肋...
+ 改用一個變數存即可

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minBuyPoint = prices[0]; // dp vector is used to save min prices
        int maxProfit = 0;
        for (int i = 1 ; i < prices.size(); i++)
        {
            minBuyPoint = min(minBuyPoint, prices[i]);
            maxProfit = max(maxProfit, prices[i] - minBuyPoint);
        }
        return maxProfit;
    }
};

### 解法分析
+ time complexity: O(n)

### 執行結果

---

## 二度改良

+ Solved on 2024/06/30 Neetcode 150 (Sliding Window)
+ 用sliding window的方式來解題!
+ 永遠讓left pointer指到最小的price，接著每次都去更新最大的profit，最後在return.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        int left = 0;
        for (int right = 1; right < prices.size(); right++)
        {
            if(prices[right] < prices[left])
            {
                left = right;
            }
            int curProfit = prices[right] - prices[left];
            res = max(curProfit, res);
        }
        return res;
    }
};

### 結果