My java solution and thinking process


  • 0
    L

    Just wanted to share this answer, as this is the 4th series in the Buy and Sell stock problem.

    The solution and the rob house is basically the same idea, answer for MSP - maximum subarray problem.

    My solution is inspired by @peterleetcode at https://discuss.leetcode.com/topic/4766/a-clean-dp-solution-which-generalizes-to-k-transactions

    Define f [ i ] as the amount / profit you can get most at kth step.

    Basically , f [ i ] is to be calculated as: f [ i ] = max( f [ i - 1 ], p [ i ] -p [ j ] + f [ j - 2 ] )

    where f [ i - 1 ] means no action take from last step to here,

    and p [ i ] - p [ j ] + f [ j - 2 ] means you took an action (purchase and sale) from j to i, with CD at j-1, thus previous profit at f [ j - 2 ], where j runs from 0 to i

    thus it's changed into:

    f [ i ] = max ( f [ i - 1 ], p [ i ] + max ( f [ j - 2 ] - p [ j ] ) )

    and here's the java code submitted

        public int maxProfit(int[] prices) {
       		if ( prices.length < 2 )
    			return 0;
       		if ( prices.length == 2 )
       		    return Math.max(0,prices[1]-prices[0]);
    		int f0=0, f1=0, f2=0;
    		f0 = 0;
    		f1 = Math.max( prices[1] - prices[0], 0 );
    		int sum = 0, minj = Math.max( -prices[0], -prices[1] );
    		for ( int i = 2; i < prices.length; i++ )
    		{
    			minj = Math.max( minj, f0 - prices[i] );
    			f2 = Math.max( f1, prices[i] + minj );
    			f0 = f1;
    			f1 = f2;
    		}
    		return f2;
        }
    

Log in to reply
 

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