Java linear time solution


  • 0
    M
    class Solution {
        public int maxProfit(int[] prices) {
            int netProfit = 0;
            if(prices.length < 1){
                return netProfit;
            }
            int buy = prices[0];
            int[] profit = new int[prices.length];
            java.util.Arrays.fill(profit, 0);
            for(int i=1;i<prices.length;i++){
                buy = Math.min(buy, prices[i]);
                int currProfit = prices[i] - buy;
                if(currProfit > 0){
                    buy = prices[i];
                }
                profit[i] = Math.max(profit[i-1], profit[i-1] + currProfit);
            }
            return profit[profit.length-1];
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.