Best Time to Buy and Sell Stock

[kokocan12]

Problem

When an array is given, each element means price of the day i, find max profit.
You can buy once, and sell once.
You can not sell stock at the same day when you bought.

example
Input: prices = [7,1,5,3,6,4]
Output: 5

Because buy at day 1(the price is 1) and sell at day 4(the price is 6), I can get profit 5.

Approach 1

We can get left-max, right-max at each day.
Then the max value of (right-max) - (left-max) is the max profit.
There is no chance in that max-value, min-value change at the same time,
so need to consider it is same day or not.

The code is below.

const maxProfit = function(prices) {
    
    let leftMin = Infinity;
    const leftMinArray = Array(prices.length).fill();
    
    for(let i=0; i<prices.length; i++) {
        leftMin = Math.min(prices[i], leftMin);
        leftMinArray[i] = leftMin;
    }
    
    let rightMax = 0;
    const rightMaxArray = Array(prices.length).fill();
    for(let i=prices.length - 1; i>=0; i--) {
        rightMax = Math.max(prices[i], rightMax);
        rightMaxArray[i] = rightMax;
    }
    
    // Is there any chance in that max-value, min-value change at the same time? No.
    // No need to consider it is sameday or not.
    let profit = 0;
    let idx = 0;
    while(idx < prices.length) {
        const min = leftMinArray[idx];
        const max = rightMaxArray[idx];
        const profitTemp = max - min;
        
        profit = Math.max(profit, profitTemp);
        idx += 1;
    }
    
    return profit;
};

Approach 2

Using two pointers.
At the beginning, set left = 0, right = 1.
Increase right to the end, until prices[left] < prices[right].
If prices[right] <= prices[left], change left index to right index, because previous data is useless anymore.

The code is below.

const maxProfit = function(prices) {
    
    let left = 0;
    let right = 1;
    let profitMax = 0;
    
    while(right<prices.length) {
        const profit = prices[right] - prices[left];
        
        if(profit <= 0) {
            left = right;
            right = left + 1;
        } else {
            profitMax = Math.max(profit, profitMax);
            right += 1;
        }
    }
    
    return profitMax;
};