[Algorithm] LeetCode 121. Best Time to Buy and Sell Stock

121. Best Time to Buy and Sell Stock

Easy

---

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

 

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

 

Constraints:

• 1 <= prices.length <= 10n5
• 0 <= prices[i] <= 10n4

 

 

이 문제는 주식을 사서 팔아서 얻을 수 있는 최대 이익을 구하는 문제로, 주어진 배열 prices에서 가장 작은 가격에 주식을 사서 그 이후에 가장 높은 가격에 주식을 팔면 됩니다. 주식을 팔기 전에는 반드시 사야하므로 이전 가격보다 작은 가격에 주식을 사는 것이 중요합니다.

 

solution:

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE; // 최소 가격
        int maxProfit = 0; // 최대 이익
        
        for (int price : prices) {
            // 현재 가격이 최소 가격보다 작으면 최소 가격을 업데이트
            if (price < minPrice) {
                minPrice = price;
            } 
            // 현재 가격에서 최소 가격을 뺀 값이 최대 이익보다 크면 최대 이익을 업데이트
            else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice;
            }
        }
        
        return maxProfit;
    }
}

 

Case [7, 2, 5, 1, 6, 4]로 예시를 들어보겠습니다.

 

• 1일째: 가격 7
• 2일째: 가격 2
• 3일째: 가격 5
• 4일째: 가격 1
• 5일째: 가격 6
• 6일째: 가격 4

주식을 사서 팔아서 얻을 수 있는 최대 이익을 계산해야 합니다.

1. 첫 번째 주식을 사는 날 (1일째, 가격 7):
   • 최소 가격(minPrice)을 7로 설정.
   • 최대 이익(maxProfit)을 0으로 초기화.
2. 두 번째 날 (2일째, 가격 2):
   • 현재 가격(2)이 최소 가격(7)보다 작으므로 최소 가격을 2로 업데이트. (2를 사는 것이 더 이득)
   • 최대 이익(maxProfit)은 여전히 0.
3. 세 번째 날 (3일째, 가격 5):
   • 현재 가격(5)이 최소 가격(2)보다 크므로 이날에 주식을 팔아 이익을 얻을 수 있음.
   • 이익은 5 - 2 = 3.
   • 최대 이익(maxProfit)을 3으로 업데이트.
4. 네 번째 날 (4일째, 가격 1):
   • 현재 가격(1)이 최소 가격(2)보다 작으므로 최소 가격을 1로 업데이트. (1을 사는 것이 더 이득)
   • 최대 이익(maxProfit)은 여전히 3.
5. 다섯 번째 날 (5일째, 가격 6):
   • 현재 가격(6)이 최소 가격(1)보다 크므로 이날에 주식을 팔아 이익을 얻을 수 있음.
   • 이익은 6 - 1 = 5.
   • 최대 이익(maxProfit)을 5로 업데이트.
6. 여섯 번째 날 (6일째, 가격 4):
   • 현재 가격(4)가 최소 가격(1)보다 크므로 이날에 주식을 팔아 이익을 얻을 수 있음.
   • 이익은 4 - 1 = 3.
   • 최대 이익(maxProfit)을 5로 유지.

주식을 산 날과 판 날을 올바르게 선택하여 얻을 수 있는 최대 이익은 5입니다.

최저가에서 사서 최고가에서 팔면서 이익을 최대화하는 전략을 따른 것입니다.