An 1ms Java DP solution, beats 90.85% of java submissions


  • 1
    B
    public int maxProfit(int[] prices) {
    		if (prices == null || prices.length <= 1) {
    			return 0;
    		}
    		int[] cache = new int[prices.length + 1];
    		int len = prices.length;
    		cache[len - 2] = prices[len - 2] < prices[len - 1] ? prices[len - 1] - prices[len - 2] : 0;
    		int i1;
    		int i2;
    		for (int i = len - 3; i >= 0; i--) {
    			int max = 0;
    			i1 = i + 1;
    			i2 = i + 2;
    			if (prices[i1] <= prices[i]) {
    				max = cache[i1];
    			} else {
    				if (prices[i2] >= prices[i1]) {
    					max = prices[i1] - prices[i] + cache[i1];
    				} else {
    				  	int v1 = prices[i1] - prices[i] + cache[i + 3];
    					int v2 = (prices[i2] > prices[i] ? prices[i2] - prices[i] : 0) + cache[i2];
    					max = v1 > v2 ? v1 : v2;
    				}
    			}
    			cache[i] = max;
    		}
    		return cache[0];
    	}
    

Log in to reply
 

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