ALL RIGHT YOU GUYS WE ARE NOT GONNA BE DOING problem one twenty one max profit.
So make sure you're terminal you're seeded into our course directory at into the exercises folder then
you're gonna run the command just LC one twenty one max profit dash dash watch this is gonna run our
test suite and our tests are failing and now we're gonna fix that on to minimize a terminal window here
and so again I want you guys to imagine that this is a list of prices for say Apple stock if you bought
Apple stock on day one for seven dollars and sold it on day three for five dollars you'd make a profit
of negative two dollars per Apple stock.
So the problem as what's the optimal day to buy and then sell to make the maximum profit and the day
you sell must always be after the day you bought it.
Now an easy way to go about solving this problem is to use nested for loops.
So for each number check all the numbers ahead of it and then subtract each number from itself.
Calculate the profit but these nested for loops in this brute force solution would give us all events
squared time complexity or quadratic time flex time complexity and in an interview setting that would
not pass.
We could actually solve this with just one loop to the input array or one for loop iteration and the
way we're going to go about doing this is this I want you guys to imagine that this is a math problem
for each number we iterate on.
Find the smallest value before it and then subtract from it.
So right five the smallest value before 5 is 1 because that's smaller than 7 5 minus 1 max profits for
it where it's 6.
What's the smallest number before the number 6.
Well it's the number one 6 minus 1 max profit.
5.
So that's where our code is going to do song let's say let max profit is equal to zero.
Initially we're going to change max profit and then have our code return that Dan will say let cheapest
priced
is equal to prices at index 0.
So remember how I said as we go through each number we're going to check for the smallest value before
the current iterated number we are on.
So at first the number seven for seven dollars the smallest price before seven is while it just itself
so cheapest price is seven dollars so we'll be the first element in the prices array.
And now let's loop over our prices array for let AIS equal to zero i.e. less than prices dot length
I plus plus to make my code easier to read.
Well let's say Conte's current price or price is equal to prices at index i.
Now let's make sure we actually have the cheapest price for our current price.
If price is less than the cheapest price.
Well we have a new cheapest price
then I'll create a variable called current profit and the current profit is the price minus the cheapest
price.
And lastly let's reassign max profit.
I'll say max profit is equal to math dot Max the current profit and then the previous max profit.
In case you guys are wanting what math that Max does is if you pass in numbers 0 give you back the biggest
one.
So we pass in 10 and 20 math that Max will turn back 20.
So I'm saying the max profit variable which we set up here is going to be whichever is bigger the current
profit or the previous calculated max profit.
Once we finish this for loop iteration we can return max profit.
I going to save and let's check that they pass our test suite.
They do.
So now let's make sure that this code passes the lead code tests
and they do.
Which is great.
And now let's go over our max profit complex the analysis time complexity is all that we iterate through
the input array just once.
No nested for loops and spaced complexity is over one idea guys that includes this video.