My approach using four states at any given time DP, JAVA


  • 0
    L
    public class Solution {
        public int maxProfit(int[] prices) {
            if (prices.length == 0) return 0;
            int[][] dp = new int[prices.length][4];
            // 0- buy, 1-hold, 2- sell, 3- nohold
            dp[0][0] = -prices[0];   // this will be money with you if you buy stock
            dp[0][1] = Integer.MIN_VALUE; // because you can't hold before you have sold any
            dp[0][2] = 0;        // you haven't sold any so no profit accumulated
            dp[0][3] = 0;        // you are at this state if you are choosing to not purchase the stock
            for (int i = 1; i < prices.length; i++) {
                dp[i][0] = dp[i-1][3] - prices[i];
                dp[i][1] = Integer.max(dp[i-1][0], dp[i-1][1]);
                dp[i][2] = Integer.max(dp[i-1][1], dp[i-1][0]) + prices[i];
                dp[i][3] = Integer.max(dp[i-1][2], dp[i-1][3]);
            }
            int ret = 0;
            for (int i = 0; i < 4; i++) {
                ret = Integer.max(dp[prices.length - 1][i], ret);
            }
            return ret;
        }
    }
    

    There are 4 states as mentioned in the comments.
    The DP defines the transition between the states.


Log in to reply
 

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