[array] best time to buy and sell stock

✅ Problem

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

• 해당 문제는 배열의 값을 그래프로 나열해 시각화 하면 해결 방식 떠올릴 때 도움 됨

 

✅ Approach & Solution

방식1) 브루트 포스, 시간복잡도 : O(n^2)

• 모든 경우의 수익을 구하게 됨

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;

        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
            }
        }
        
        return maxProfit;
    }
}

 

방식2) 저점과 현재 값과의 차이 계산, 시간복잡도 : O(n)

• 저점과 최대 수익 계산을 for문 안에서 연달아 수행

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int minPrice = prices[0]; // 임시로 첫 번째 값 지정

        for (int price : prices) {
            minPrice = Math.min(minPrice, price); // 지금까지의 저점 계산
            maxProfit = Math.max(maxProfit, price - minPrice);
        }

        return maxProfit;
    }
}