Explanation of why the editorial solution approach 2 works.


  • 0
    V

    The below solution is inspired by the editorial solution approach 2. I could not figure it out myself. An explanation of why this solution works follows the solution.

    public int maxProfit(int[] prices) {
            if(prices==null || prices.length==0) return 0;
            int i=0, profit=0;
            while(i<prices.length){
                while(i<prices.length-1 && prices[i+1]<=prices[i]) i++;
                int valley = prices[i++];
                while(i<prices.length-1 && prices[i+1]>=prices[i]) i++;
                if(i<prices.length)
                    profit += prices[i]-valley;
            }
            return profit;
        }
    

    Initially I was unable to wrap my head around this solution. I understood what was being done, but I failed to understand why it is the correct solution as I thought that it may not work for some test cases. My way of approaching this problem was by drawing a comparison between the profit that can be gained by using multiple transactions and the profit that can be gained by using a single transaction in the same given range. The above solution never does that. So why does it work?

    Well, it works because of common sense. In a given range of prices, the profit gained by a single transaction will never exceed the profit from multiple transactions. Below is an extreme case where profit from a single transaction equals the profit from multiple transactions:

    [1,2,2,3,3,4]
    Max profit: 3 in any manner.

    Except for such cases, a single transaction can never generate the same profit as multiple transactions in a given range. Things become clearer if you draw a graph.

    So a comparison need not be drawn. Multiple transactions will always yield more profit.

    This is an attempt to help anyone confused by the solution like I was. Please correct me if I made any mistake.


Log in to reply
 

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