[LeetCode][릿코드][Python][#122] Best Time to Buy and Sell Stock II

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

Best Time to Buy and Sell Stock II - LeetCode

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

---

최대 1주의 주식만을 소유할 수 있고 주식을 팔고 당일에 바로 다시 살 수 있으므로 주식을 사고 이익이 발생하면 바로 파는 방법, 탐욕 알고리즘(Greedy Algorithms)을 이용하여 최대 이익을 만들 수 있다. 

 

예제 1 입력을 생각해 보면 다음과 같다.

최대 수익을 낼 수 있는 방법은 2일에 1원에 사고, 3일에 5원에 팔아 4(5-1)의 이익을 내고, 다시 4일에 3원에 사고, 5일에 6원에 팔아 3(6-3)의 이익을 내어 총 7원의 이익을 내는 것이다.

 

예제 2 입력을 생각해 보면 다음과 같다.

단순히 생각했을 때는 1일에 1원에 사고, 5일에 5원에 팔아 4의 이익을 내는 것이 최적인 것 같지만, 이는 1일에 1원에 사고 2일에 2원에 팔아 1(2-1)의 이익을 내고, 2일에 2원에 사고 3일에 3원에 팔아 1(3-2)의 이익을 내고, 3일에 3원에 사고 4일에 4원에 팔아 1(4-3)의 이익을 내고, 4일에 4원에 사고 5일에 5원에 팔아 1(5-4)의 이익을 내 총 4의 이익을 내는 방법이 탐욕 알고리즘을 사용한 방법이다.

다시 말해, N번째 날에 주식을 사서 N+1번째 날에 팔아 이익이 난다면, 주식을 사고 그렇지 않으면 사지 않는 것이다.

 

이를 코드로 구현하면 다음과 같다.

class Solution:
    def maxProfit(self, prices) -> int:
        return sum(max(prices[i+1] - prices[i], 0) for i in range(len(prices) - 1))