Java DP Solution.


  • 0
    public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<2) return 0;
        int[] dp=new int[prices.length];
        int minPrice=prices[0];
        dp[0]=0;
        for(int i=1;i<prices.length;i++){
            //compare to the minPrice;
           //if greater than the minPrice, then get the max of the dp[i-1] and prices[i]-minPrice
           //if smaller, then remain the dp[i-1]
            if(prices[i]>=minPrice){
                dp[i]=Math.max(dp[i-1],prices[i]-minPrice);
            }
            else{
                minPrice=prices[i];
                dp[i]=dp[i-1];
            }
        }
        return dp[prices.length-1];
    }
    

    }


Log in to reply
 

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