121. Best Time to Buy and Sell Stock

class Solution {
    public int maxProfit(int[] prices) {
        int curprofit = 0;
        int maxprofit = 0;
        
        if (prices.length <= 0) {
            return 0; 
        }
        
        int bought = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < bought) {
                bought = prices[i];
            } else {
                curprofit = prices[i] - bought;
                if (curprofit > maxprofit) {
                    maxprofit = curprofit; 
                }
            }
        }
        
        return maxprofit;
        
    }
}

Runtime: 1 ms, faster than 97.43% of Java online submissions for Best Time to Buy and Sell Stock.

Memory Usage: 38.9 MB, less than 26.28% of Java online submissions for Best Time to Buy and Sell Stock.

나쁘진 않아서 만족~

O(n)

Solution 보니 2개의 for loop 아님 나와 완전 똑같은 방식으로 푼다

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

Kadane's Algorithm이라는데 처음 뵙는 분, 하지만 이걸 적용시키면 Best Time to Buy and Sell Stock II (전에 풀었던 문제)와 같은 아이디어로 풀 수 있따