[leetcode] - 121. Best Time to Buy and Sell Stock

problem

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

Best Time to Buy and Sell Stock - LeetCode

You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Constraints:

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

---

Access

1. brute force (O(n^2))

The problem has constraints 10^5. so, run loop 10^10 on a rough estimate.

I think this solution gets a timeout.

 

so, we need another solution as more efficient.

 

2. O(n)

We should buy cheap and sell expensive. and time has go direction.

ex) prices: [7,1,5,3,6,4]
7 -> 1 -> 5 -> 3 -> 6 -> 4

We just need the lowest price, when current day.

and we calculate the current price - min price until previous.

function maxProfit(prices: number[]): number {
    let result = 0;
    let min = 10000;

    for(let i=0; i<prices.length; i++){
        //currentPrice - minPrice until previous
        const currentPrice = prices[i];
        result = Math.max(result, currentPrice-min);
        
        //and save minPrice until current
        min = Math.min(min, currentPrice);
    }
    
    //this result is max profit, because all case calcurate and compare in previous loop function
    return result;
};