Day008 - 122. Best Time to Buy and Sell Stock II

122. Best Time to Buy and Sell Stock II

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

내 풀이

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        total_profit = 0

        for i in range(len(prices)-1):
            current_profit = prices[i+1] - prices[i] # "i+1번째 가격 - i번째 가격"으로 current_profit을 구함
            
            if current_profit > 0:             # current_profit이 0보다 크면(판매가가 구매가보다 크다면)
                total_profit += current_profit # total_profit에 해당 차액을 더해줌

        return total_profit

주어진 stock의 prices중에서 가장 큰 이득을 볼 수 있는 구매/판매 시기를 구하던 어제 문제의 업그레이드 버전이다.

주어진 prices list에서 주식을 구매/판매 횟수에 제한이 없이(단 두 개 이상의 주식을 동시에 보유할 수 없다) 최대 profit을 구하는 문제인데, 언제나 그렇듯 가장 먼저 떠오르는건 brute-force인데, 딱 봐도 \(O(N^2)\)이기 때문에 통과가 안될 것이다.

결국 주어진 prices list를 한 번만 순회하는 \(O(N)\)으로 해결해야 하는데, 간단하게 하루씩 확인하면서 수익이 나는 모든 구간의 수익을 더한 값을 구하는 것으로 해결하였다.

예를 들어보면…

prices : [1,4,7,8,6,4]

1. 구매가 1, 판매가 8 (1, 8)일 경우의 profit : 7
2. 하루씩 확인하여 이득이 생기는 모든 경우를 더한다면 (1, 4), (4, 7), (7, 8), total_profit = 3 + 3 + 1 = 7

결국 복잡하게 계산할 것 없이 하루씩 계산해서 생기는 모든 이득을 더해주면 간단하게 해결이 가능하다!

# Time Complexity : \(O(N)\)