[Array/String] Best Time to Buy and Sell Stock

1. 문제

LeetCode - Best Time to Buy and Sell Stock

• 매일 변동하는 물건의 가격이 적혀 있는 배열 prices가 주어졌을 때, 물건을 산 뒤 팔았을 때 최대 이윤을 반환하는 문제
• 이윤을 낼 수 없을 때는 0을 반환

2. 접근법

• 단순 이중 반복문으로 최대 이윤을 업데이트 한 뒤 반환하고, 이윤이 없을 시 0을 반환하도록 접근
• 테스트 케이스 212개 중 203개 통과, 그러나 배열의 길이가 큰 경우에는 Time Limit 초과
• 더 좋은 성능의 알고리즘이 필요
• 찾아보니 카데인 알고리즘을 활용하면 O(n)의 시간 복잡도로 해결 가능 -> 개선

3. 풀이(실패 -> 시간 초과)

class Solution {
    public int maxProfit(int[] prices) {
        // 1. 최대 수익 max 선언 및 0으로 초기화
        int max = 0;

        // 2. 이중 반복문으로 최대 수익 업데이트
        for (int i = 0; i < prices.length; i++) {
            int currentProfit = 0;

            for (int j = i + 1; j < prices.length; j++) {
                currentProfit = prices[j] - prices[i];

                if (currentProfit > max) {
                    max = currentProfit;
                }
            }
        }

        // 3. max 리턴
        return max;
    }
}

4. 성능

- Runtime : 시간 한도 초과 -> 2ms

- Memory : N/A -> 60.9mb

5. 개선

• 카데인 알고리즘(Kadane's Algorithm)을 활용해 해결
• 시간 복잡도를 O(n*n) -> O(n)으로 개선

class Solution {
    public int maxProfit(int[] prices) {
        // 브루트 포스 시간 한도 초과 O(n*n), 더 나은 방법 찾기
        // 카데인 알고리즘 -> O(n)

        // 1. 최대 수익 maxProfit 및 최소 가격을 기억하기 위한 minPrice
        int maxProfit = 0; // 수익이 없을 수 있으므로 0으로 초기화
        int minPrice = prices[0]; // 첫번째 가격으로 초기화

        // 2. 배열 prices를 순회하면서 maxProfit 및 minPrice 업데이트
        for (int i = 1; i < prices.length; i++) {
            int profit = prices[i] - minPrice;
            
            maxProfit = Math.max(maxProfit, profit);
            minPrice = Math.min(minPrice, prices[i]);
        }

        // 3. maxProfit 리턴
        return maxProfit;
    }
}