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

121. Best Time to Buy and Sell Stock

LeetCode

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.

prices[i]가 i번째 날의 주식 가격인 배열 prices가 주어집니다.
주식을 매수할 하루를 고르고, 미래의 다른 날을 골라 해당 주식을 매도하여 이익을 극대화하고자 합니다.
이 거래에서 얻을 수 있는 최대 이익을 반환하세요. 만약 어떠한 이익도 얻을 수 없다면 0을 반환하세요.

 

Example

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.

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

---

1. 문제 요구사항 분석

배열에서 가장 낮은 숫자를 찾고, 그 이후에 가장 높은 숫자를 찾는 문제

 

2. 접근 전략

😭  배열 하나를 돌면서 min, max를 찾은 후, min과 max의 위치를 비교하면 됨 => 문제점: min 이후의 조금이라도 더 큰 max 값을 찾으면 되기 때문에 요구사항에 맞지 않음

😄  배열 한 번을 돌면서 오늘이 min인지 확인, 맞다면 min 값 변경, 아니라면 이익 계산하여 기존 이익의 최댓값과 비교 → O(n)

 

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price: prices) {
            if (minPrice > price) {
                minPrice = price;
            } else if (maxProfit < price - minPrice) {
                maxProfit = price - minPrice;
            }
        }

        return maxProfit;
    }
}

 

조금 더 깔끔한 코드 :) 

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            maxProfit = Math.max(maxProfit, price - minPrice);
        }

        return maxProfit;
    }
}