LeetCode) 121. Best Time to Buy and Sell Stock

121. Best Time to Buy and Sell Stock

예전에 채널코퍼레이션 코딩테스트에서 풀었던 문제의 기초가 되는 문제. 그때는 여러 조건이 섞여있어서 dp가 사용되었지만 이번에는 dp는 사용되지않고, 한번 순환으로 해결이 된다.

배열을 돌면서 최소값을 갱신해가면서 현재 인덱스와의 값의 차이가 max가 되는 값을 구하면 된다.

class Solution {
    public int maxProfit(int[] prices) {

        int start = (int)Math.pow(10,5);
        int maxValue = -1;

        for(int i=0; i<prices.length; i++){
            
            if(start > prices[i]){
                start = prices[i];
            }
            maxValue = Math.max(maxValue,prices[i] - start);

        }
        return maxValue;
    }
}