Java Step by step with example, tell you why this could be solved without DP


  • 0

    /*
    Idea is based on dp, but really there is no point to keep track of the history.
    Serveal fields is enough.

    Say stock is:
    3,2,6,5,0,3

    Init the array to be 0
    0,0,0,0,0,0
    each index represents the max of whehter to buy or sell or hold on that day

    day1:
    0,0,0,0,0,0

    day2:
    it's a decreasing, not buy in
    0,0,0,0,0,0

    day3:
    it's increasing from day 2, buy,
    0,0,4,0,0,0

    day4:
    It's decrease, now have 2 options: if day3 did buy hold, if day3 didn't buy, use the max profit before day3
    hold: 3
    max profit before day 3: 0
    choose hold
    0,0,4,3,0,0

    day5
    Decrease again.
    hold from day 4: - 2
    max profit before day4: 4 on day3
    choose the value at day3.
    0,0,4,3,4,0

    day6
    increase. definately buy
    0,0,4,3,4,7

    Max is 7
    */

    public class Solution {
        public int maxProfit(int[] prices) {
            if(prices.length < 2) return 0;
            int firstDay = 0;
            int secondDay = 1;
            int max = 0;
            int secondMax = 0;
            int profit_so_far = 0;
            if(prices[secondDay] > prices[firstDay]){
                max = prices[secondDay] - prices[firstDay];
                secondMax = 0;
                profit_so_far = max;
                firstDay++;
                secondDay++;
            }
            while(secondDay < prices.length){
                int yesterday = profit_so_far;
                if(prices[secondDay] > prices[firstDay]){
                    profit_so_far = Math.max(profit_so_far + prices[secondDay] - prices[firstDay], max);
                }else{
                    profit_so_far = Math.max(profit_so_far + prices[secondDay] - prices[firstDay], secondMax);
                }
                if(profit_so_far > max){
                    max = profit_so_far;
                }
                secondMax = Math.max(secondMax, yesterday);
                firstDay++;
                secondDay++;
            }
            return max;
    
        }
    }```

Log in to reply
 

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