[Array & Hash] Best Time to Buy and Sell Stock

문제

주식의 가격이 일별로 주어진 배열 prices가 있습니다. 여기서 prices[i]는 i번째 날의 주식 가격을 나타냅니다. 하루를 선택해서 한 주식을 구매하고, 미래의 다른 날에 그 주식을 판매함으로써 이익을 극대화하고자 합니다. 이 거래에서 달성할 수 있는 최대 이익을 반환하십시오. 만약 어떠한 이익도 달성할 수 없다면, 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.

---

나의 풀이

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
           
        for (int i = 0; i < prices.length-1; i++) {
            for (int j = i+1; j < prices.length; j++) {
                if (prices[j] - prices[i] > profit) {
                   profit = prices[j] - prices[i];
                } 
            }
        }
        return profit;
    }
}

• 숫자 두개를 선택하여 이익을 계산하는 방법
• O(N^2) 만큼의 시간이 소요

---

다른 풀이

이 문제에서 확실한건, 반드시 구매해야 판매할 수 있다는 점.
즉, 판매 시점에서는 이전 가격 중 가장 작은 값과 비교하면 된다!

그럼 첫 날에는 팔 수 없고, 두 번째 날부터 팔 수 있음.

int minPrice = prices[0]; // 최소 가격
int maxProfit = 0; // 최대 이익

// 1. 배열 순회하며 최솟값 minPrice 업데이트 하기
for (int i = 1; i<prices.length; i++) {
    if (minPrice > prices[i]) {
        minPrice = prices[i];
    } else {
       // 2. 판매 시점에서 최솟값과 비교하여 maxProfit 에 저장
       maxProfit = Math.max(maxProfit, prices[i] - minPrice);
    }
}

// 3. 최종 maxProfit 을 반환
        return maxProfit;

• 배열을 한번만 순회하면서 찾기 때문에 O(n) 시간 복잡도
• Math.max(pram1, pram2) : 인자1과 인자2 중 큰 값을 리턴