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.