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


  • 0

    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];
        }
    }
    

Log in to reply
 

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