PROBLEMS / 121 / EASY
BEST TIME TO BUY AND SELL STOCK
EASY
VIEW ON LEETCODEPROFITISWIN
BUY ON ONE DAY, SELL ON A LATER ONE, FOR THE BIGGEST PROFIT. CARRY THE LOWEST PRICE SEEN SO FAR AS THE BUY, AND AT EVERY DAY MEASURE THE SALE AGAINST IT, KEEPING THE BEST.
THE IDEA
YOU CANNOT SELL BEFORE YOU BUY, SO ONLY THE LOWEST PRICE BEHIND TODAY IS WORTH BUYING AT. CARRY THAT LOWEST AS YOU GO, AND EACH DAY OFFERS ONE CANDIDATE SALE: TODAY MINUS THE LOWEST SO FAR. THE BEST OF THOSE WINS.
FRAME1 / 4
5
1
4
2
6
PRICES OVER TIME. BUY LOW, SELL HIGH, BUT THE BUY MUST COME FIRST.
WATCH IT RUNPRICES: 7, 1, 5, 3, 6, 4
THE BLUE TILE IS THE BUY, THE LOWEST PRICE SO FAR. THE RAISED TILE IS THE SELL, SCANNING RIGHT. EACH DAY ARCS A CANDIDATE PROFIT FROM BUY TO SELL, AND A NEW RECORD GOLDS THE PAIR. WHEN A PRICE DIPS BELOW THE BUY, THE BUY MOVES THERE.
SPEEDSTEP0 / 7
PRICES:
BUY
70
1
1
5
2
3
3
6
4
4
5
THE QUESTION THIS STEP
PRESS PLAY
STARTSTART WITH THE FIRST PRICE AS THE BUY. HUNT A BIGGER SELL LATER.
1def max_profit(prices):2 max_p = 03 min_buy = prices[0]4 for sell in prices:5 max_p = max(max_p, sell - min_buy)6 min_buy = min(min_buy, sell)7 return max_p
SELL-
BUY7
PROFIT-
MAX0
THE COST
O(N)TIME
ONE LEFT TO RIGHT PASS.
O(1)SPACE
ONLY TWO NUMBERS ARE CARRIED, THE LOWEST BUY SO FAR AND THE BEST PROFIT.