## Problem

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

:::spoiler **Optimal Space & Time Complexity**

- Time complexity:
- Space complexity:

:::

<br>

## Thoughts & Solutions

### 東

:::spoiler Code

var maxProfit = function(prices) {
    let maxProfit = 0;
    let buyIdx = 0;
    let sellIdx = 1;
    while ((buyIdx < sellIdx) && (sellIdx < prices.length)){
        const buyPrice = prices[buyIdx];
        const sellPrice = prices[sellIdx];
        let currProfit = sellPrice - buyPrice;
        
        if(currProfit > maxProfit){
            maxProfix = currProfit;
        }
        
        const profitForMoveBuyRight = currProfit - buyPrice + prices[buyIdx + 1];
        const profitForMoveSellRight = currProfit - sellPrice + prices[sellIdx + 1];
        if(profitForMoveBuyRight > profitForMoveSellRight){
            buyIdx++;
        } else {
            sellIdx++;
        }
    }
    return maxProfit;
};

:::

<hr/>

### Hao
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/solutions/1735550/python-javascript-easy-solution-with-very-clear-explanation/

1. 直覺會覺得使用左右指針來做，left 找最小值，right 找最大值
2. 更新的邏輯
1. Fix left
1. Right > left => update maxProfit
2. Right < left => left = right
* 解題重點：可以直接更新是因為這個為目前所見最小值！
2. Loop ends when right < prices.length

:::spoiler Code

:::

<hr/>

### YC
- left-right pointer
- left pointer is for min value
- maxProfit: `prices[left] < prices[right]`
- update the pointer:
- left pointer: when `prices[left] > prices[right]`
- right pointer: in each loop

:::spoiler Code

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let left = 0;
    let right = 1;
    let maxProfit = 0;
    while(right < prices.length){
        if(prices[left] < prices[right]){
            const profit = prices[right] - prices[left];
            maxProfit = Math.max(maxProfit, profit);
        }
        else{
            left = right;
        }

        right++;
    }
    return maxProfit;
};

:::

<hr/>

### Sol

[7, 1, 5, 3, 6, 4]

1. The difference between two numbers, I need two pointers.
2. How to compare the two pointers?
- [7, 1]: 7 > 1, I can directly skip 7; 1 would get a greater profit.
- [1, 5]: 1 < 5, this could be the maximum profit.

:::spoiler Code

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let maxProfit = 0;
    let first = 0;
    let second = 1;
    while(second < prices.length){
       if(prices[first]< prices[second]){
            const profit = prices[second] - prices[first];
            if(profit > maxProfit) {
                maxProfit = profit;
            }
        }else{
            first = second;
        }
        second++;
    }
    return maxProfit;
};

:::

<br>

## Supplement / Discussion

## Live Coding

:::spoiler (東)

var maxProfit = function(prices) {
    let maxProfit = 0;
    let buyIdx = 0;
    let sellIdx = prices.length - 1;
    while (buyIdx < sellIdx){
        const currBuyPrice = prices[buyIdx];
        const currSellPrice = prices[sellIdx];
        const currProfit = currSellPrice - currBuyPrice;
        
        if(currProfit > maxProfit){
            maxProfit = currProfit;
        }
        
        const profitForMoveBuyRight = currSellPrice - prices[buyIdx + 1] 
        const profitForMoveSellLeft = -currBuyPrice + prices[sellIdx - 1] 
        
        if(profitForMoveBuyRight > profitForMoveSellLeft){
            buyIdx++;
        } else {
            sellIdx--;
        }
    }
    return maxProfit;
};```
:::