문제

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.

구현 전 예상 풀이

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

구현 코드

예상 풀이는 시간초과에서 걸린다.
가장 가격이 적은 가격만 비교하는걸로 알고리즘을 변경했다.

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int minPrice = prices[0];
        for (int i = 1; i < prices.length; i++) {
            int price = prices[i];
            int profit = price - minPrice;
            
            maxProfit = Math.max(maxProfit, profit);
            
            minPrice = Math.min(minPrice, price);
        }

        return maxProfit;
    }
}

121. Best Time to Buy and Sell Stock