99클럽 코테 스터디 39일차 - DP

문제

Best Time to Buy and Sell Stock

풀이

• 최소값과 최대값 차이가 가장 컸을 때를 구하면 된다
• 최대 10의 5승까지라서 O(n)으로 풀어야 한다
• 순회를 하면서 min과 max를 동시에 구하기

코드

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

정리