122 Best Time to Buy and Sell Stock II
122 Best Time to Buy and Sell Stock II
문제
You are given an array
priceswhereprices[i]is the price of a given stock on theithday.
Find the maximum profit you can achieve. You may complete as many transactions as you like
(i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
pricesprices[i]: i번째 날의 주가- 동시여 여러 트랜잭션 불가. 반드시 주식을 다시 사기 전에 팔아야 한다
조건
- 1 <= prices.length <= 3 * 10^4
- 0 <= prices[i] <= 10^4
예제
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e., max profit = 0.
해결
1st
1 생각
- 탐욕 알고리즘은 부분 최적해가 전체 최적해가 되는 경우 가능
[7,1,5,3,6,4]- 7일 때 안 산다
- 1일 때 산다(가격이 내려감)
- 5일 때 판다(+4)
- 3일 때 산다(가격이 내려감)
- 6일 때 판다(+3)
이익: 7
[1,2,3,4,5]- 1일 때 산다
- 2일 때 안 판다(가격이 오름)
- 3일 때 안 판다(가격이 오름)
- 4일 때 안 판다(가격이 오름)
- 5일 때 판다(+4)
이익: 4
- 분기 처리
구매: 전날보다 가격이 내려간 경우유지: 다음날과 그 다음날 가격이 올라간 경우판매: 다다음날 가격이 내려감
7 *
6 sell
5 sell
4 *
3 buy
2
1 buy
0 1 2 3 4 5
5 sell
4 유지
3 유지
2 유지
1 buy
0 1 2 3 4
1 코드
def maxProfit_1st(self, prices: List[int]) -> int:
'''
- `구매`: 전날보다 가격이 내려간 경우
- `유지`: 다음날 가격이 올라간 경우
- `판매`: 다음날 가격이 내려감
'''
prices_len = len(prices)
if prices_len == 0:
return 0
idx_max = prices_len - 1
idx = 0
profit = 0
current = 0
is_bought = False
while idx < prices_len:
if (idx + 1 <= idx_max and prices[idx] > prices[idx + 1]) or idx == idx_max: # 다음날 가격이 내려감
if is_bought:
profit += prices[idx] - current
is_bought = False
elif idx > 0 and prices[idx - 1] > prices[idx] and prices[idx] < prices[idx + 1]: # 전날보다 가격이 내려가고, 다음날 가격이 올라감
if not is_bought:
is_bought = True
current = prices[idx]
elif prices[idx] < prices[idx + 1]: # 다음날 가격이 올라감
if not is_bought:
is_bought = True
current = prices[idx]
idx += 1
return profit
def maxProfit_2nd(self, prices: List[int]) -> int:
'''
- `구매`: 전날보다 가격이 내려간 경우
- `유지`: 다음날 가격이 올라간 경우
- `판매`: 다음날 가격이 내려감
'''
prices_len = len(prices)
if prices_len == 0:
return 0
idx = 0
profit = 0
current = 0
is_bought = False
while idx < prices_len:
if (idx + 1 < prices_len and prices[idx] > prices[idx + 1]) or idx == prices_len - 1: # 다음날 가격이 내려감 또는 끝에 도달
if is_bought: # 구매한 주식이 있으면 판매
profit += prices[idx] - current
is_bought = False
# 없으면 스킵
elif not is_bought and prices[idx] < prices[idx + 1]: # 전날보다 가격이 내려가고, 다음날 가격이 올라감
is_bought = True
current = prices[idx]
idx += 1
return profit
1 결과: 성공
Runtime: 64 ms, faster than 39.90% of Python3 online submissions for Best Time to Buy and Sell Stock II.
Memory Usage: 15.1 MB, less than 62.96% of Python3 online submissions for Best Time to Buy and Sell Stock II.
2nd 책 풀이
2 코드
def maxProfit(self, prices: List[int]) -> int:
result = 0
for i in range(len(prices) - 1):
if prices[i + 1] > prices[i]: # 트랜잭션은 이뤄진다고 치고, 올라가는 값만 계산
result += prices[i + 1] - prices[i]
return result
# 파이썬다운 방식
def maxProfit_3rd(self, prices: List[int]) -> int:
return sum(max(prices[i + 1] - prices[i], 0) for i in range(len(prices) - 1))
2 결과: 성공
Runtime: 56 ms, faster than 88.88% of Python3 online submissions for Best Time to Buy and Sell Stock II.
Memory Usage: 14.9 MB, less than 98.03% of Python3 online submissions for Best Time to Buy and Sell Stock II.