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

• 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[] sell = new int[3];
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.
}
return sell[(prices.length-1)%3];
}
``````

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