# DFS+Cache, convert to DP based on DFS+Cache, space optimized from O(n) to O(1)

• count=1 means first buy, count=2 means first sell, count=3 means second buy, count=4 means second sell. Return when count==5

``````public class Solution {
int[][] cache;
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
cache = new int[prices.length][6];
return search(prices, 0, 1);
}

private int search(int[] A, int idx, int count) {
if (count == 5 || idx > A.length - 1) return 0;
if (cache[idx][count] != 0) return cache[idx][count];

int cur = A[idx], ret = 0;
int left = search(A, idx + 1, count + 1);
int right = search(A, idx + 1, count);
if (count == 1 || count == 3)
ret = Math.max(left - cur, right);
else if (count == 2 || count == 4)
ret = Math.max(left + cur, right);

cache[idx][count] = ret;
return ret;
}
}
``````

Switch to DP based on the above DFS. Because F[i][j] depends on F[i+1][j+1] and F[i+1][j], so we iterate from right to left.

``````public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int[][] F = new int[prices.length + 1][6];
for (int i = prices.length - 1; i >= 0; i--) {
for (int j = 5; j >= 1; j--) {
if (j == 5) F[i][j] = 0;
else {
int left = F[i + 1][j + 1];
int right = F[i + 1][j];
if (j == 1 || j == 3)
F[i][j] = Math.max(left - prices[i], right);
else if (j == 2 || j == 4)
F[i][j] = Math.max(left + prices[i], right);
}
}
}
return F[0][1];
}
}
``````

Optimized space:

``````public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int[][] F = new int[2][6];
for (int i = prices.length - 1; i >= 0; i--) {
for (int j = 5; j >= 1; j--) {
if (j == 5) F[i % 2][j] = 0;
else {
int left = F[(i + 1) % 2][j + 1];
int right = F[(i + 1) % 2][j];
if (j == 1 || j == 3)
F[i % 2][j] = Math.max(left - prices[i], right);
else if (j == 2 || j == 4)
F[i % 2][j] = Math.max(left + prices[i], right);
}
}
}
return F[0][1];
}
}
``````

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