본문으로 바로가기
Tag그리디 알고리즘
Tags
사이트Leet code
이해완벽히 이해
난이도level 1
메모그리디 기본
발행 여부
최종 편집 일시
푼 날짜
Categoryps/그리디 알고리즘

문제 해설 및 주의사항

원문

You are given an integer array prices where prices[i] is the price of a given stock on the ith 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 * 104
  • 0 <= prices[i] <= 104

번역 및 주의사항

  • prices[i] : i 번째 날에 i stock 의 가격을 나타낸다.
  • 최대 하나의 주식만 가질 수 있다.
  • 이때, 최대 이익을 구하여라.

풀이

  • 그리디 알고리즘을 떠올렸다.
    • 두 가지 상황이 있다.
      1. 현재 주식 가격 < 내일 주식 가격
        1. 내일 주식 가격 - 현재 주식 가격 만큼 이득을 취한다.
      1. 현재 주식 가격 ≥ 내일 주식 가격
        1. 아무것도 하지 않는다.

내 풀이 코드

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
반응형