Best Time to Buy and Sell Stocks - Finding Max Profit

Problem Description

Say you have an array, A, for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Return the maximum possible profit.

Problem Constraints

0 <= A.length<= 700000
1 <= A[i] <= 10⁷

Example Input / Output

Input 1:
A = [1, 2]
Output:
1

Input 1:
A = [1, 4, 5, 2, 4]
Output:
4

---

Let us assume, you are buying the stock on i^th day. When would you like to sell it?
The answer is, we would like to sell when price of the stock is highest on or after i^th day.
That means, we need to find the maximum element on the right hand side.

So, for every i^th index find maximum on right side and calculate the profit. Maximum profit will be the answer.

Solution Approach

If you buy your stock on day i, you’d obviously want to sell it on the day its price is maximum after that day.
Now this part can be done as:

• Start processing entries from the end maintaining a maximum till start. and do the same from start maintaining the minimum till end Constant additional space requirement.

• Store the values as in the same array like [min,max]

• Run another loop on the modified array to find the max profit

maxProfit : function(A){
        let profit = 0;
        let max = Number.NEGATIVE_INFINITY;
        let min = Number.POSITIVE_INFINITY;

        for(let i=A.length-1;i>=0;i--){
            max = Math.max(max,A[i])
           A[i] = [A[i],max]
        }
        for(let i=0;i<A.length;i++) {
            min = Math.min(min,A[i][0]);
            A[i][0] = min
        }

        for(let i=0;i<A.length;i++) {
            profit = Math.max(A[i][1]-A[i][0],profit)
        }
        return profit
    }