3) Stock Profits

Stock profits on leet code

This one didn’t go very well. This was my solution:

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    profit = 0
    let reductionArray = [...prices]
 
    for (let i = 0; i < prices.length - 1; i++){
      let currentVal = prices[i]
      reductionArray.shift()
      let highVal = Math.max(...reductionArray)
      let difference = highVal - currentVal
      if (difference > profit){
        profit = highVal - currentVal
      } else {
      }
    }
    return profit
};
 
console.log(maxProfit([7,1,5,3,6,4]))

This is like, at least a 50 minute solution. I DID get a working solution after 30 minutes, but it timed out. I thought I could weasel my way out of O(n^2) complexity with Math.max, but that’s obviously still a for loop. That was sort of wishful thinking.

So my second implementation didn’t fix much.

Claude gave me this incredibly simple solution:

var maxProfit = function(prices) {
    let minPrice = Infinity;
    let maxProfit = 0;
    
    for (let price of prices) {
        if (price < minPrice) {
            minPrice = price;
        } else if (price - minPrice > maxProfit) {
            maxProfit = price - minPrice;
        }
    }
    
    return maxProfit;
};

Let me walk through it with comments:

var maxProfit = function(prices) {
    let minPrice = Infinity; // oh wow didn't know that existed
    let maxProfit = 0; // familiar
    
    for (let price of prices) { // nice, just a for of, in order
        if (price < minPrice) { // get the lowest price so far
            minPrice = price; // save it
        } else if (price - minPrice > maxProfit) {
        // BUT IF NOT THE LOWEST PRICE, check and see if minPrice
        // i.e. LOOKING BACKWARDS at the most attractive starting point
        // yields best profit
        // The else if here is a really extra but nice optimization
        // This could just be two separate conditionals
        // But it's true that they are mutually exclusive
            maxProfit = price - minPrice;
        // And damn. That's it.
        }
    }
    
    return maxProfit;
};

So looking at Claude’s answer, it’s like I was stuck in this “looking forwards” paradigm. But there was this looking backwards option the whole time and I was too stuck in my O(n2) bullshit to realize it.

The difference has TWO sides - it requires a high number farther up, and a lower number farther down. We’re looking, fundamentally, for the largest range, as long as that range goes low high in the same direction as the array progresses.