2ms Mod Rolling array DP based on dietpepsi's Algorithm


  • 0
    F

    Really enjoyed dietpepsi's thought on his DP algorithm. Link to dietpepsi's post

    It took me sometime to understand his neat code in realizing this algs, so I only changed his real O(1) to this always-work space optimization technology for no-brainer: simply use mod rolling array. Especially asked for space optimization during interview.

    The mod rolling array is a general 1-sec change to improve the space from O(N) to O(1). eg: here the sell[] is based on 2 previous sell[], so I declare sell[3]. In terms of buy[], it's on based on previous buy[], so buy[2] is enough.

    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2)  return 0;
    
        int[] buy = new int[2];
        int[] sell = new int[3];
        buy[0] = -prices[0];
        buy[1] = Math.max(-prices[0], -prices[1]);
        sell[0] = 0;
        sell[1] = Math.max(0, prices[1]-prices[0]);
        for (int i = 2; i < prices.length; ++i) {
          buy[i%2] = Math.max(sell[(i-2)%3]-prices[i], buy[(i-1)%2]);  // the way to use mod rolling array.
          sell[i%3] = Math.max(buy[(i-1)%2]+prices[i], sell[(i-1)%3]);
        }
        return sell[(prices.length-1)%3];
    }
    

Log in to reply
 

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