Share my java solution with key annotation, 4ms DP


  • 1
    N

    public class Solution {

    public static int maxProfit(int[] prices) {
    	if (prices.length == 0)
    		return 0;
    	int p = 0, buy = 0, sell;
    	int[] a = new int[prices.length];//a[i] indicates the max profit before (and including) i th day with at most one transaction
    	int[] b = new int[prices.length];//b[i] indicates the max profit after (and including) i th day with at most one transaction
    	for (int i = 1; i < prices.length; i++) {
    		int temp = prices[i] - prices[buy];
    		if (temp > p) {
    			p = temp;
    			sell = i;
    		}
    		else if (temp < 0)
    			buy = i;
    		a[i] = p;
    	}
    	
    	sell = prices.length - 1;
    	p = 0;
    	for (int i = prices.length - 2; i >= 0; i--) {
    		int temp = prices[sell] - prices[i];
    		if (temp > p) {
    			p = temp;
    			buy = i;
    		}
    		else if (temp < 0)
    			sell = i;
    		b[i] = p;
    	}
    	
    	for (int i = 1; i < prices.length - 2; i++) {
    		int temp = a[i] + b[i + 1];
    		if (temp > p)
    			p = temp;
    	}
    	
    	/*for (int i = 0; i < prices.length; i++)
    		System.out.println(a[i]);
    	System.out.println("\n");
    	for (int i = 0; i < prices.length; i++)
    		System.out.println(b[i]);
    	System.out.println("\n");*/
    	
        return p;
    }
    

    }


Log in to reply
 

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