121. Best Time to Buy and Sell Stock

The Magician Of the Wall Street

Today, we are a trader, who has a computer that can predict the future and return you the list of stock prices this week. Your task is to return the maximum profit that week. For instance,

For prices = [7,1,5,3,6,4], you will return 5 as that is the maximum profit. Buying at a point in time and selling it at the highest price. You buy when its price is 1, and sell at 6 for the maximum profit. Therefore, the max profit is 5.

The BruteForce Method

Obviously, you can painstakingly go through every possible outcome, like Dr Strange did to find which one is the best. Then you submit the max Profit. But that is really inefficient with a time complexity of O(n²). A much better solution is given below.

The O(n) solution

Let us see what do we want? We want the maximum profit possible. How do we find the maximum profit possible? It is the Difference between the largest value and the smallest value, given that the smallest value is behind the largest value.

The Approach

We start with two variables, one to track the maxProfit and another one to keep track of the lowest number. We then iterate through the list. If we find that the profit from the current-lowest is greater than the max profit, we will replace it. Also, if we find that a number is smaller than our smallest number, we will replace its value. As we iterate through the code, we will eventually find the maxProfit.

C++

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        int maxProfit = 0;
        int minVal = prices[0];
        for(int i=0;i<prices.size();i++)
        {
            int profit = prices[i]-minVal;
            if(maxProfit<profit)
                maxProfit = profit;
            else if(minVal>prices[i])
                minVal = prices[i];
        }
        return maxProfit;
    }
};

Rust

impl Solution {
    pub fn max_profit(prices: Vec<i32>) -> i32 
    {
        let mut maxProfit:i16 = 0;
        let mut cDay:i16 = prices[0] as i16;
        for price in prices
        {
            let price = price as i16;
            let profit = price -cDay;
            if(profit>maxProfit)
            {
                maxProfit = profit;
            }
            else if(cDay>price)
            {
                cDay = price;
            }
        }
        maxProfit as i32
    }
}

JavaScipt

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