1주차 - 121. Best Time to Buy and Sell stock [코딩 인터뷰 공부]

121. Best Time to Buy and Sell stock

주어진 prices array 의 prices[i] 는 i 번째 날의 주식 가격이다.

최대의 이익을 return 하시오. 이익을 낼 수 없는 경우 0을 return.

 

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

 

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

.

.

.

.

.

.

.

n = len(p)
max_so_far = 0

for i in range(n):
    for j in range(i+1,n):
        max_so_far = max(max_so_far, p[j] - p[i])

return max_so_far

런타임: 시간 초과

시간 복잡도: O(n^2)

공간 복잡도: O(1)

 

l = 0 # left
r = 1 # right
m = 0 # max

while r < len(prices):
    if prices[l] < prices[r]:
        c = prices[r] - prices[l] # current price
        m = max(c, m)
    else:
        l = r
    r += 1

return m

런타임: 903 ms, 82.87%

메모리 사용: 22.7 MB, 29.78%

 

 

max_profit, min_price = 0, prices[0]
for p in prices:
    min_price = min(min_price, p)
    profit = p - min_price
    max_profit = max(max_profit, profit)
return max_profit

런타임: 939 ms, 77.70%

메모리 사용: 22.6 MB, 53.95%