Tag | 그리디 알고리즘 |
---|---|
Tags | |
사이트 | Leet code |
이해 | 완벽히 이해 |
난이도 | level 1 |
메모 | 그리디 기본 |
발행 여부 | |
최종 편집 일시 | |
푼 날짜 | |
Category | ps/그리디 알고리즘 |
문제 해설 및 주의사항
원문
You are given an integer array prices
where prices[i]
is the price of a given stock on the i
th
day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Example 1:
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.
Total profit is 4 + 3 = 7.
Example 2:
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.
Total profit is 4.
Example 3:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
Constraints:
1 <= prices.length <= 3 * 10
4
0 <= prices[i] <= 10
4
번역 및 주의사항
prices[i]
: i 번째 날에 i stock 의 가격을 나타낸다.
- 최대 하나의 주식만 가질 수 있다.
- 이때, 최대 이익을 구하여라.
풀이
- 그리디 알고리즘을 떠올렸다.
- 두 가지 상황이 있다.
- 현재 주식 가격 < 내일 주식 가격
내일 주식 가격 - 현재 주식 가격
만큼 이득을 취한다.
- 현재 주식 가격 ≥ 내일 주식 가격
- 아무것도 하지 않는다.
- 현재 주식 가격 < 내일 주식 가격
- 두 가지 상황이 있다.
내 풀이 코드
class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0
for day in range(len(prices) - 1):
if prices[day] < prices[day + 1]:
res += prices[day + 1] - prices[day]
return res
반응형
'ps > 그리디 알고리즘' 카테고리의 다른 글
[Leet code] 406. Queue Reconstruction by Height (0) | 2022.02.04 |
---|---|
[level 2] 조이스틱 (0) | 2021.10.31 |
잃어버린 괄호 1541 (0) | 2021.10.31 |
가장 긴 증가하는 부분 수열 2 (LIS) (0) | 2021.10.31 |
[우선순위 큐] 순회 강연 2109 (0) | 2021.10.31 |