Java DP solution


  • 0
    N
    // f(i) is the profit of the ith day
    
    // f(i) = f(i-1) + (a[i]-a[i-1]), f(n-1)>0
    // f(i) = a[i]-a[i-1],            f(n-1)<=0
    // i = 1...n
    
    public class Solution {
        public int maxProfit(int[] prices) {
            if(prices ==null || prices.length <2) return 0;
            
            int profit = 0;
            int max =0;
            int len = prices.length;
            
            for(int i=1;i<len;i++){
                if(profit <= 0){
                    profit = prices[i]-prices[i-1];
                }else{
                    profit += (prices[i]-prices[i-1]);
                }
                if(profit > max) max = profit;
            }
            
            return max;
        }
    }

Log in to reply
 

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